题意

已知三个数 $c,d,x$ ，求有多少对正整数 $a,b$ 满足 $c\times lcm(a,b)- d\times gcd(a,b) = x$。

题解

显然，$gcd(a,b)|lcm(a,b)$，所以我们设 $lcm(a,b)=t\times gcd(a,b)$，那么就可以化简原式为：

直接枚举一下 $gcd(a,b)$ 的值，然后推出 $t$ 的值。

问题转化为已知 $gcd(a,b),lcm(a,b)$ 的值，求 $a,b$ 的方案数。

将 $t$ 分解为 $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$ 那么每个质数要么放到 $a$ 中去，要么放到 $b$ 中去，所以答案就是 $2^n$。

暴力分解时间复杂度是 $O(\sqrt t )$ 的，并不能通过此题。

发现这个分解质因数后质数的个数可以直接欧拉筛，然后就做完了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e7+5;
int _,f[N],p[N],b[N],cnt;
void work(int maxn){
    for(int i=2;i<=maxn;i++){
        if(!b[i])p[++cnt]=i,f[i]=1;
        for(int j=1;j<=cnt&&p[j]*i<=maxn;j++){
            b[i*p[j]]=1;
            if(i%p[j]==0)f[i*p[j]]=f[i];
            else f[i*p[j]]=f[i]+1;
        }
    }
    for(int i=0;i<=maxn;i++)f[i]=(1<<f[i]);
}
int main() {
    std::ios::sync_with_stdio(false);
    cin>>_;
    work(2e7);
    while(_--){
        int c,d,x,ans=0;
        cin>>c>>d>>x;
        for(int i=1;i*i<=x;i++){
            if(x%i==0){
                if((x/i+d)%c==0){
                    int t=(x/i+d)/c;
                    ans+=f[t];
                }
                if(i*i!=x){
                    if((i+d)%c==0){
                        int t=(i+d)/c;
                        ans+=f[t];
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}