用gcd(a,b)=x,则a/x⊥b/x的性质推导出x/a1⊥a0/a1,b1/x⊥b1/b0,枚举b1的约数暴力跑即可。
意识到一个问题,这个粗陋的输出外挂不能输出0。
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } inline ll rdll(){ ll ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } int n; ll gcd(ll x,ll y){ return y==0?x:gcd(y,x%y); } void out(ll x){ if(!x)return; out(x/10); putchar('0'+x%10); } inline void solve(){ ll a0,a1,b0,b1; a0=rdll();a1=rdll();b0=rdll();b1=rdll(); ll a=a0/a1,b=b1/b0,ans=0; for(ll i=1;i*i<=b1;i++){ if(b1%i)continue; ll t=b1/i; if(i%a1==0&&gcd(i/a1,a)==1&&gcd(b,b1/i)==1)ans++; if(i*i==b1)continue; if(t%a1==0&&gcd(t/a1,a)==1&&gcd(b,b1/t)==1)ans++; } if(ans)out(ans),putchar(' '); else puts("0"); } int main(){ n=rd(); while(n--){ solve(); } return 0; }