【Luogu】P1072Hankson的趣味题（gcd）

这题真TM的趣味。

可以说我的动手能力还是不行，想到了算法却写不出来。以后说自己数论会GCD的时候只好虚了……

我们首先这么想。

x与a0的最大公约数为a1，那么我们把x/=a1,a0/=a1之后，x和a0不会再有除了1之外的公约数。

证明：设x/a1=c,a0/a1=d.

若有gcd(c,d)=y 则有p=c/y，q=d/y.

反之c=py,d=qy.

则有x=pya1,a0=qya1。

则x和a0共有公约数ya1。

y属于正实数集，因此ya1>a1.

因此gcd(x,a0)=ya1。

又因为gcd(x,a0)=a1,所以假设与推出结果相矛盾，因此得出那行带颜色的结论。

同样可以得出结论：b1=b0,b1/x两数也不应该有除了1之外的公约数。

证明方式参考上面。

代码如下

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

long long gcd(long long a,long long b){
    if(b==0)    return a;
    return gcd(b,a%b);
}

int main(){
    int T=read();
    while(T--){
        int ans=0;
        int a=read(),b=read(),c=read(),d=read();
        for(int i=1;i*i<=d;++i){
            if(!(d%i)){
                if(!(i%b)&&gcd(a/b,i/b)==1&&gcd(d/c,d/i)==1)    ans++;
                int j=d/i;
                if(i==j)    continue;
                if(!(j%b)&&gcd(a/b,j/b)==1&&gcd(d/c,d/j)==1)    ans++;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}

【Luogu】P1072Hankson的趣味题（gcd）

相关推荐