P1072Hankson 的趣味题解题报告

这题其实也很简单（可能是当时计算机算的慢），就是要满足那两个式子,并且从gcd和lcm我们可以知道,i为a1整数倍且为b2因子，然后枚举的时候注意不要枚举到底了，记得求素数的时候吗？只用枚举到sqrt(b1)就行。 然后你就会发现不对，因为a和b太大了啊！要缩小（……）比如gcd(x,y)=a，那gcd(x/a,y/a)==1（这个还挺好想的吧） 然后就有一个TLE了……然后先改快读，然后优化一下速度，再用快写，噫，好，我过了！ ```cpp #include<cstdio> #include<iostream> #include<cmath> using namespace std; int n,sum; long long a0,a1,b0,b1,t,a2,b2,j; int gcd(int x,int y){return !y?x:gcd(y,x%y);} inline void read(long long &x) { x=0; long long f(0);char ch=getchar(); while(!isdigit(ch))f|=(ch=='-'),ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=f?-x:x; } inline void write(int x) { char s[30]; int top(0); while(x) s[++top]=x%10, x/=10; if(!top) putchar('0'); else while(top) putchar(s[top--]+'0'); } int main() { scanf("%d",&n); while(n--) { read(a0);read(a1);read(b0);read(b1); a2=a0/a1;b2=b1/b0;sum=0; for(int i=1;i*i<=b1;i++) if(b1%i==0) { if(gcd(b2,b1/i)==1&&gcd(i/a1,a2)==1&&i%a1==0) sum++; j=b1/i; if(j==i) continue; if(gcd(b2,b1/j)==1&&gcd(j/a1,a2)==1&&j%a1==0) sum++; } write(sum);printf("\n"); } return 0; } ```