求满足 gcd(a,n)*acd(b,n)=n^k的整数对（a,b）。n<=10^9

特殊情况考虑一下（n=1,k>=2），问题很容易转化为求euter(n/g)*euter(g),g是约数。这题比赛时候竟然应该不会求n的约数二不会做！

求约数时候，枚举（1，根号n），另一半对应啊！欧拉函数，这次有改进。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long euler(int n)
{
    long long ans=n;
    for(long long i=2;i<=sqrt(n*1.0);i++)          //就按塌陷的n！
    {
        if(n%i==0)
        {
            ans=ans*(i-1)/(i*1.0);
            while(n%i==0)n/=i;
        }
    }
     if(n!=1)ans=ans*(n-1)/n;
    return ans;
}
const long long  mod=1000000007;
int main()
{
    long long n,k;
    while(~scanf("%I64d%I64d",&n,&k))
    {
       if(n==1) {printf("1\n");  continue;}
       if(k>2)  {printf("0\n");  continue;}
       if(k==2) {printf("1\n");  continue;}
       else
        {
           long long ans=0;
            for(long long i=1;i*i<=n;i++)       //枚举约数，只要根号n内，（根号n，n）必然对应之
            {
                if(n%i==0)
                {
                    long long x=n/i;
                    if(i*i!=n)
                     ans+=euler(i)*euler(x)*2%mod;
                    else
                     ans+=euler(i)*euler(x)%mod;

                   ans=ans%mod;
                }
            }
         printf("%I64d\n",ans);
        }
    }
    return 0;
}

hdu4983 / 枚举约数+欧拉函数