cf Educational Codeforces Round 106 D. The Number of Pairs

本文主要是介绍cf Educational Codeforces Round 106 D. The Number of Pairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
D. The Number of Pairs
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given three positive (greater than zero) integers c, d and x.

You have to find the number of pairs of positive integers (a,b) such that equality c⋅lcm(a,b)−d⋅gcd(a,b)=x holds. Where lcm(a,b) is the least common multiple of a and b and gcd(a,b) is the greatest common divisor of a and b

.
Input

The first line contains one integer t (1≤t≤10^4) — the number of test cases.

Each test case consists of one line containing three integer c, d and x (1≤c,d,x≤10^7).
Output

For each test case, print one integer — the number of pairs (a,b) such that the above equality holds.
Example
Input
Copy

4
1 1 3
4 2 6
3 3 7
2 7 25

Output
Copy

4
3
0
8

Note

In the first example, the correct pairs are: (1,4), (4,1), (3,6), (6,3).

In the second example, the correct pairs are: (1,2), (2,1), (3,3).

中文：

给你c，d，x三个数，让你找出满足下面
c⋅lcm(a,b)−d⋅gcd(a,b)=x 这个方程的所有(a,b)的对数。

代码：

    #include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 2e7 + 3;int t,c,d,x;vector<int> f;int pow2[35];int prim_factor[maxn];int tmp[maxn];int gcd(int a,int b){if(a%b==0)return b;return gcd(b,a%b);}void get_factor(vector<int>& v, int k){for (int i=1; i * i <= k; i++){if (k % i == 0){v.push_back(i);if ( k != i * i){v.push_back(k/i);}}}//v.push_back(k);}int cnt_prim_factor(int k){int cnt = 0;int i = 2;while(k != 1){if (k % i == 0){cnt++;while(k%i == 0){k=k/i;}}i++;}return cnt;}int main(){ios::sync_with_stdio(false);memset(tmp, -1, sizeof(tmp));memset(prim_factor, 0, sizeof(prim_factor));tmp[1]=1;for (int i=2;i<maxn;i++){if (tmp[i] == -1){for (int j=i;j<maxn;j+=i){if (tmp[j] == -1){tmp[j] = i;}}}}for (int i=2;i<maxn;i++){int j = i / tmp[i];prim_factor[i] = prim_factor[j] + (tmp[i] != tmp[j]);}pow2[0] = 1;for (int i=1;i<=30;i++){pow2[i] = pow2[i-1] * 2;}cin>>t;while(t--){cin>>c>>d>>x;int fac = gcd(c,d);fac = gcd(fac, x);c/=fac;d/=fac;x/=fac;f.clear();get_factor(f, x);int ans = 0;for (int i=0;i<f.size();i++){int ab = x / f[i] + d;//cout<<"ab = " << ab <<" f = " <<f[i] << " d = " <<d<<endl;if (ab % c ==0){ab= ab / c;int tmp = prim_factor[ab];ans += pow2[tmp];}}cout<<ans<<endl;}return 0;}

解答：

首先要想到(a,b)这两个数的gcd和lcm的关系，a × b / gcd(a,b) = lcm(a,b)，如果a × b / gcd(a,b) / gcd(a,b)，那么可以表示成
a×b = p1 × p2 × gcd(a,b) × gcd(a,b)，其中p1和p2是两个互质的数。按照这个原则，把下面的方程变换一下，即左右除以gcd(a,b)，有：

c⋅lcm(a,b)−d⋅gcd(a,b)=x
变成
c × p1 × p2 - d = x / gcd(a,b)
再变换一下
p1×p2 = (x / gcd(a,b) + d) / c
可以看出，就是找等号后面表达式是否成利，并且中有多少个互质的p1和p2
其中要求x / gcd(a,b)能除开，那么就要求gcd(a,b)必须是x的因子。
现在枚举x的因子，那么可以得到等号右边的表达式，设(x / gcd(a,b) + d) / c = k
根据唯一分解定理，可以将k分解成 $q_1^{n1}q_2^{n2}q_3^{n3}....q_x^{n_y}$ ，要想p1和p2两个数互质，那只要保证从分解出来的这些 $q_1$ 到 $q_x$ 这x个数分成两堆，一堆组成p1，剩下的一堆组成p2即可，取数的方法是 $C_{x}^{0} + C_{x}^{1} +...+C_{x}^{x} = 2^x$
把所有枚举的因子都计算一次上面的分解计数并累加，最后就是答案