题目链接：http://codeforces.com/contest/776/problem/E
题意： 有三个函数 f(n) g(n) Fk(n)，已知 n, k，求Fk(n)的值
题解： 我们首先讨论 k=1 时的情况，此时我们的任务变成了求以下方程 x,y 的对数（对数就是 f(n)） 这个 x,y 的对数可以使用欧拉函数 phi() 来表示（证明略），结果为 phi(n)，然后我们惊奇的发现g(n)恒等于n。 那么我们的任务又变成了求k次 phi(n)，这个十分容易，直接暴力即可。（令i = 1..n且i为奇数，我们只需要求出phi(i) 即可，时间复杂度并不高。） P.S：需要开long long。
代码：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int inf = 1 << 26; LL phi(LL n) { LL ans = 1; // phi(1) = 1 for ( LL i = 2; i*i <= n; i ++ ) { if(n%i) continue; LL p = i-1; n /= i; while(n%i == 0) { n /= i; p *= i; } ans *= p; } if(n != 1) ans *= (n-1); return ans; } const LL mod = 1000000007; int main(){ LL n, k; scanf("%I64d %I64d", &n, &k); for ( int i = 1; i <= k && n != 1; i ++ ){ if(i%2 == 1) { n = phi(n); } } printf("%I64d\n", n%mod); return 0; }