题目大意：给你N和K,问有多少个数对满足gcd(N-A,N)*gcd(N-B,N)=N^K。
题解：由于 gcd(a, N) <= N,于是 K>2 都是无解,K=2 只有一个解 A=B=N,只要考虑K=1的情况就好了其实上式和这个是等价的gcd(A,N)*gcd(B,N)=N^K,我们枚举gcd(A,N)=g,那么gcd(B,N)=N/g。问题转化为统计满足 gcd(A, N)=g的A的个数。这个答案就是 ?(N/g)，只要枚举 N 的 约数就可以了。答案是 Σ?(N/g)*?(g)（g|N）。

#include <cstdio>typedef long long LL;const int MOD=1000000007;LL Eular(LL n){    LL ret=1;    for(LL i=2;i*i<=n;i++){        if(n%i==0){            n/=i,ret*=i-1;            while(n%i==0)n/=i,ret*=i;        }    }if(n>1)ret*=(n-1);    return ret;}int main(){    int n,k;    while(~scanf("%d%d",&n,&k)){        if(n==1||k==2){puts("1");continue;}        if(k>2){puts("0");continue;}        LL ans=0;        for(LL i=1;i*i<=n;i++)if(n%i==0){            LL t=Eular(i)*Eular(n/i)%MOD;            (ans+=t)%=MOD;            if(i*i!=n)(ans+=t)%=MOD;        }printf("%d\n",(int)ans);    }return 0;}

HDU 4983 Goffi and GCD