题解 P1072 【Hankson 的趣味题】

这道题是一道入门数学题 用线性筛筛出sqrt（2000000000）质数 枚举b1的质因子 用dfs求出每一个约数 根据。。。。一个int的约数最多有1536个 所以直接判断即可 因为我搜的时候 第一个裸质因数可能重复 所以用Map来解决重复问题就结束了 时间复杂度上限O（T*1536*log（1536）） ```cpp //code by luotc #include<bits/stdc++.h> using namespace std; #define int long long inline int read(){ int x=0,f=1; char p=getchar(); while(!isdigit(p)){ if(p=='-') f=-1; p=getchar(); } while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar(); return x*f; } const int maxn=1e6+5; int n,prime[maxn],v[maxn],cnt,tot[maxn],cnt1,a[maxn],cnt2,a0,a1,b0,b1,ans; inline void shaifa(int n){ for(int i=2;i<=n;i++){ if(!v[i]){ v[i]=1; prime[++cnt]=i; } for(int j=1;j<=cnt&&prime[j]*i<=n;j++){ v[prime[j]*i]=prime[j]; if(i%prime[j]==0) break; } } } inline int gcd(int x,int y){ if(x%y==0) return y; else return gcd(y,x%y); } inline void dfs(int dep,int sum){ if(b1%sum!=0) return; a[++cnt2]=sum; dfs(dep,sum*tot[dep]); if(dep+1>cnt1) return; // dfs(dep+1,sum*tot[dep+1]); dfs(dep+1,sum); } signed main(){ n=read(); shaifa(1000000); for(int i=1;i<=n;i++){ map<int,int> Map; a0=read(),a1=read(),b0=read(),b1=read(); int x=b1;cnt1=0;cnt2=0;ans=0; for(int j=1;j<=cnt;j++){ if(prime[j]*prime[j]>b1) break; if(b1%prime[j]==0){ tot[++cnt1]=prime[j]; } } for(int j=1;j<=cnt1;j++) while((x!=1)&&(x%tot[j]==0)) x/=tot[j]; if(x!=1) tot[++cnt1]=x; if(cnt1!=0) dfs(1,1); else a[++cnt2]=1; // for(int j=1;j<=cnt1;j++){ // cout<<tot[j]<<" "; // } // cout<<endl; // for(int j=1;j<=cnt2;j++){ // cout<<a[j]<<" "; // } for(int j=1;j<=cnt2;j++){ if(Map[a[j]]) continue; Map[a[j]]=1; int x=gcd(a0,a[j]); if(x!=a1) continue; x=gcd(a[j],b0); if(b0*a[j]/x!=b1) continue; ans++; } printf("%lld\n",ans); } return 0; } ``` 还记得去年被此题吊打。。。