题目链接：http://codeforces.com/problemset/problem/776/E
${\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$，所以直接暴力做就可以了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 10010
#define llg long long
#define md 1000000007
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); llg phi(llg x)
{
llg m=sqrt(x+0.5);
llg ans=x;
for (llg i=;i<=m;i++)
if (x%i==)
{
ans=ans/i*(i-);
while (x%i==) x/=i;
}
if (x>) ans=ans/x*(x-);
return ans;
}
llg n,m,k; int main()
{
yyj("E");
cin>>n>>k;
llg ans=phi(n);
for (llg i=;i<=k;i++)
{
if (i%) ans=phi(ans);
if (ans==phi(ans)) break;
}
cout<<ans%md;
return ;
}