Hankson的趣味题

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define spider signed
using namespace std;
const int N=5e4+10;
int pm[N],cnt;
bool h[N];
struct Factor{
    int p, s;
}f[10];
int ft,dv[1601], dt;
void init(int n){
    for(int i=2;i<=n;i++){
        if(!h[i])pm[cnt++]=i;
        for(int j=0;pm[j]*i<=n;j++){
            h[pm[j]*i]=true;
            if(i%pm[j]==0)break;
        }
    }
}
void dfs(int u,int p){
    if(u==ft){
        dv[dt++]=p;
        return;
    }
    for(int i=0;i<=f[u].s;i++){
        dfs(u+1,p);
        p*=f[u].p;
    }
}
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
spider main(){
    init(N-1);
    int n;
    cin>>n;
    while(n--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        ft=0;
        int t=d;
        for(int i=0;pm[i]<=t/pm[i];i++){
            int p=pm[i];
            if(t%p==0){
                int s=0;
                while(t%p==0)t/=p,s++;
                f[ft++]={p,s};
            }
        }
        if(t>1)f[ft++]={t, 1};
        dt=0;
        dfs(0,1);
        int res=0;
        for(int i=0;i<dt;i++){
            int x=dv[i];
            if(gcd(a,x)==b&&c*x/gcd(c,x)==d)res++;
        }
        cout<<res<<endl;
    }
}