题目链接：

---

${\because gcd(i,n-i)=1\Leftrightarrow gcd(i,n)=1}$

${\therefore f(x)=\phi (x)}$

${\because \sum_{d|x}\phi(d)=x}$

${\therefore g(x)=x}$

问题转换为求${\phi(\phi(\phi(...)))}$嵌套${\left \lfloor \frac{k}{2} \right \rfloor}$层。

考虑这样的嵌套至多${log}$次就会到$1$，所以直接暴力做就可以了。

---

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 1001010 #define llg long long 11 #define md 100000000712 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);13 14 15 llg phi(llg x)16 {17 llg m=sqrt(x+0.5);18 llg ans=x;19 for (llg i=2;i<=m;i++)20 if (x%i==0)21 {22 ans=ans/i*(i-1);23 while (x%i==0) x/=i;24 }25 if (x>1) ans=ans/x*(x-1);26 return ans;27 }28 llg n,m,k;29 30 int main()31 {32 yyj("E");33 cin>>n>>k;34 llg ans=phi(n);35 for (llg i=2;i<=k;i++)36 {37 if (i%2) ans=phi(ans);38 if (ans==phi(ans)) break;39 }40 cout<