题面(点击可查看)

(1<=n<=2000)

(1<=a_0,a_1,b_0,b_1<=10^9×2)

(a,b)=>gcd(a,b)，[a,b]=>lcm(a,b)

首先理解题意。给出数据(a,b,c,d)，求满足((a,x)=b,[c,x]=d)的所有x的个数。

从条件([c,x]=d)入手，我们可以发现x是d的约数。

于是首先考虑暴力做法，枚举所有x的约数，挨个判断是否满足题目条件，但是不用说，2*1e9的数据铁定T飞。

那么怎么优化呢？

我们可以看到，在我们在求每一组d的所有约数的时候，我们都一定花费了(sqrt(d))的时间复杂度，而d的范围又比较大，再加上(n)最大可以到2000，所以我们考虑通过其他方式来求得d的所有约数。

于是考虑先对d进行质因式分解，把d拆成(d=p_1^{s_1}×p_2^{s_2}×...×p_n^{s_n})的形式，其中p为每个质因子，s为每个质因子的次数。这个比较好求，只需要预先把范围以内的质数全部用线性筛过一遍，然后挨个试除，如果有质数p是d的质因子，那就用while循环求出p的次数s即可。

另外，需要注意的是，如果在所有的质因子都已经试除完毕，d的值还大于1，说明他自己也是一个质数（不能通过质数相乘得到），再记录一组{p,s}即{d,1}。注意这里的d是已经被试除过很多次了，所以已经不是输入时候的值了，实现的时候要注意最好先把d存储下来在进行试除，这样不会影响到后面的判断。

接下来我们就可以通过一次暴搜来求得d的所有约数（质因子相乘）并存储下来，作为(a,x)=b,[c,x]=d的x的值的范围，然后枚举判断即可。

#include<bits/stdc++.h>
using namespace std;
int pr[50010],cnt;
bool st[50010];
struct node
{
    int p,s;//质因数和次数
}f[1610];
int fcnt;
void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])pr[++cnt]=i;
        for(int j=1;pr[j]*i<=n;j++)
        {
            st[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/(gcd(a,b))*b;}
int dv[50010],dcnt;
void dfs(int u,int p)//质因子数组下标,x
{
    if(u==fcnt)//搜索结束
    {
        dv[++dcnt]=p;
        return;
    }
    for(int i=0;i<=f[u].s;i++)
    {
        dfs(u+1,p);
        p*=f[u].p;
    }
}
int main()
{
    int n;
    init(50005);
    cin>>n;
    while(n--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        fcnt=0;
        int t=d;
        for(int i=1;pr[i]<=t/pr[i];i++)
        {
            int p=pr[i];
            if(t%p==0)
            {
                int s=0;
                while(t%p==0)
                {
                    t/=p,s++;
                }
                f[fcnt++]={p,s};
            }
            
        }
        if(t>1)f[fcnt++]={t,1};//t本身也是质数
        dcnt=0;
        dfs(0,1);
        int ans=0;
        for(int i=1;i<=dcnt;i++)
        {
            int x=dv[i];
            if(gcd(a,x)==b&&lcm(c,x)==d)ans++;//当前x合法，答案计数加一
        }
        printf("%d
",ans);
    }
    return 0;
}