加盟网站制作定制,网页设计制作多少钱,即时热榜,企业网站建设规划可行性分析登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;有q次询问#xff0c;每次给出三个整数k#xff0c;c#xff0c;n#xff0c;求有多少满足条件的数对#xff08;a#xff0c;b#xff09;满足kabc且c是b的倍数#xff0c;且gcd(a,b)n
1q100;…登录—专业IT笔试面试备考平台_牛客网
题目大意有q次询问每次给出三个整数kcn求有多少满足条件的数对ab满足kabc且c是b的倍数且gcd(a,b)n
1q100;1k,c,n1e9
思路如果我们知道一个b那么就能找到与之唯一对应的一个a而b是c的因数也就是b不会超过sqrt(c)个所以我们可以枚举c的所有因数注意检查是否符合题目条件
//#include__msvc_all_public_headers.hpp
#includebits/stdc.h
using namespace std;
typedef long long ll;
int gcd(int a, int b)
{//求最大公因数return b ? gcd(b, a % b) : a;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin t;while (t--){ll k, c, n;cin k c n;int ans 0;for (int i 1; i * i c; i){//枚举c的因数if (c % i 0){ll b1 i, b2 c / i;if ((c - b1) % k 0){ll a1 (c - b1) / k;if (!a1)continue;if (gcd(a1, b1) n){ans;}}if ((c - b2) % k 0){//两端的倍数一起算ll a2 (c - b2) / k;if (!a2)continue;if (gcd(a2, b2) n){ans;}} }}cout ans endl;}return 0;
}
