Hankson 的趣味题

从$lcm(b,x)=d$可知$x$一定整除$d$，即$x$一定是$d$的约束。通过试除法，我们可以在$O(sqrt(N))$内求出所有$d$的约数，逐一判断是否满足题意即可。
总时间复杂度$O(n?sqrt(d)?logd)$

// luogu-judger-enable-o2
#include <iostream>
using namespace std;
long long n;
long long a,b,c,d;
int tot;
long long ans[200010];
void pri(long long n)
{for(int i=1;i*i<=n;i++){if(!(n%i)) {ans[++tot]=i;if(n/i!=i) ans[++tot]=n/i;}}
}
long long gcd(long long a,long long b)
{return b?gcd(b,a%b):a; 
}
long long lcm(long long a,long long b)
{return a*b/gcd(a,b);
}
int nod;
int main()
{cin>>n;while(n--){tot=0;cin>>a>>c>>b>>d;pri(d);nod=0;for(int i=1;i<=tot;i++){if(gcd(ans[i],a)==c&&lcm(ans[i],b)==d){nod++;	}}cout<<nod<<endl;}
}