原题：
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 n 1 q 2 n 2 q 3 n 3 . . . . q x n y q_1^{n1}q_2^{n2}q_3^{n3}....q_x^{n_y} q1n1​q2n2​q3n3​....qxny​​，要想p1和p2两个数互质，那只要保证从分解出来的这些 q 1 q_1 q1​到 q x q_x qx​这x个数分成两堆，一堆组成p1，剩下的一堆组成p2即可，取数的方法是 C x 0 + C x 1 + . . . + C x x = 2 x C_{x}^{0} + C_{x}^{1} +...+C_{x}^{x} = 2^x Cx0​+Cx1​+...+Cxx​=2x
把所有枚举的因子都计算一次上面的分解计数并累加，最后就是答案

这题有个坑点，需要打出每个数的素因子的个数表，按照程序中的打表方法不会超时。