大概吧(
题目即是求:
根据扩展欧拉定理,对于 ,有
其中 表示 内与 互质的整数个数。
注意到 迭代减小得很快,而这里的指数又非常大,可以看成是无数层。
因此设函数
则有 ,边界是 。
递归求解即可。
对了,感觉就算有 个箭头答案也是 罢(半恼
#include<bits/stdc++.h> #define int long long using namespace std; int phi[1010]; int qpow(int A, int B, int P){ int C = 1; while(B){ if(B & 1) C = C * A % P; A = A * A % P, B >>= 1; } return C; } void get_phi(){ phi[1] = 1; for(int i = 2; i <= 1000; i++){ if(phi[i]) continue; for(int j = i; j <= 1000; j += i){ if(!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } } } int solve(int x){ if(x == 1) return 0; return qpow(114514, phi[x], x) * qpow(114514, solve(phi[x]), x) % x; } signed main(){ get_phi(); cout << solve(1000); return 0; }