Cirno‘s Perfect Equation Class 2023牛客暑期多校训练营5 D

登录—专业IT笔试面试备考平台_牛客网

题目大意：有q次询问，每次给出三个整数k，c，n，求有多少满足条件的数对（a，b）满足ka+b=c且c是b的倍数，且gcd(a,b)>=n

1<=q<=100;1<=k,c,n<=1e9

思路：如果我们知道一个b，那么就能找到与之唯一对应的一个a，而b是c的因数，也就是b不会超过sqrt(c)个，所以我们可以枚举c的所有因数注意检查是否符合题目条件

//#include<__msvc_all_public_headers.hpp>
#include<bits/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;
}