【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=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long gcd(long long a,long long b){

    if(b==)    return a;

    return gcd(b,a%b);

}

int main(){

    int T=read();

    while(T--){

        int ans=;

        int a=read(),b=read(),c=read(),d=read();

        for(int i=;i*i<=d;++i){

            if(!(d%i)){

                if(!(i%b)&&gcd(a/b,i/b)==&&gcd(d/c,d/i)==)    ans++;

                int j=d/i;

                if(i==j)    continue;

                if(!(j%b)&&gcd(a/b,j/b)==&&gcd(d/c,d/j)==)    ans++;

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

【Luogu】P1072Hankson的趣味题（gcd）

最新文章

热门文章