$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 用线性筛先预处理出所有质数
2. 对 d 进行质因数分解
3. 对于这些质数，预处理出所有可能的约数
4. 枚举所有约数，判断该约数是否满足条件
5. lcm(a, b) = a * b / gcd(a, b)

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N = 50010;

int primes[N],cnt;
bool st[N];
PII factor[10];
int fcnt;
int divisor[1610],dcnt;

//线性筛
void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

//预处理出所有约数
void dfs(int u,int p)
{
    if(u==fcnt)
    {
        divisor[dcnt++]=p;
        return;
    }

    for(int i=0;i<=factor[u].second;i++)
    {
        dfs(u+1,p);
        p*=factor[u].first;
    }
}

//求最大公约数
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    //先预处理出所有质数
    init(N-1);

    int T;
    cin>>T;

    while(T--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;

        //质数个数要清空
        fcnt=0;

        //分解质因数，并统计每个质因子的个数
        int t=d;
        for(int i=0;primes[i]<=t/primes[i];i++)
        {
            int p=primes[i],s=0;
            if(t%p==0)
            {
                while(t%p==0)
                {
                    t/=p;
                    s++;
                }
                factor[fcnt++]={p,s};
            }
        }

        //较大的质因子
        if(t>1) factor[fcnt++]={t,1};

        //清空约数个数
        dcnt=0;

        //预处理出所有可能的约数
        dfs(0,1);

        //判断该约数是否满足条件
        int res=0;
        for(int i=0;i<dcnt;i++)
        {
            int x=divisor[i];
            if(gcd(a,x)==b&&(LL)c*x/gcd(c,x)==d) res++;
        }

        cout<<res<<endl;
    }

    return 0;
}