题目链接：

题意：

定义f(1)=1，f(n),n>1的值为满足x+y=n且gcd(x,y)=1的(x,y)个数；定义g(n)=Σd|n f(n/d)；定义Fk(n)满足k=1时Fk(n)=f(g(n))，k>1且k mod 2=0时Fk(n)=g(Fk-1(n))，k>1且k mod 2=1时Fk(n)=f(Fk-1(n)) 。给出n,k，求Fk(n)mod 1000000007。（1<=n,k<=10^12）

题解：

f(n)等同于求满足gcd(x,n-x)=1的x的个数，又因为gcd(x,n-x)=gcd(x,n)，所以f(n)就是phi(n)。通过观察发现g(n)=n，所以Fk(n)就是对n做(k+1)/2遍phi。每次n^0.5暴力，n=1时停止就可以了，因为n>2时，phi(n)必为偶数，偶数的phi又必然减少一半，所以复杂度大约是O(n^0.5*logn)。

以上题解转自http://www.cnblogs.com/ditoly/p/CF400.html。

其实观察出g(n)=n后，剩下的就是欧拉函数的暴力了。

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4  5 const int P=1000000007; 6  7 ll eular(ll n) 8 { 9     ll ret=1,i;10     for(i=2;i*i<=n;i++)11     {12         if(n%i==0)13         {14             n/=i,ret*=i-1;15             while(n%i==0)n/=i,ret*=i;16         }17     }18     if(n>1)ret*=n-1;19     return ret;20 }21 22 ll f(ll n,ll k)23 {24     if(n==1)return 1;25     if(k==1)return eular(n);26     return f(eular(n),k-1);27 }28 29 int main(){30     ll n,k;31     scanf("%I64d%I64d",&n,&k);32     printf("%I64d\n",f(n,(k+1)/2)%P);33     return 0;34 }