题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=3884
题意：
定义$f(p)=2^{2^{2^{2^{…^2}}}}(\ mod \ p)$，求$f(p)$，其中$2$有无穷多个，$1 \leq p \leq 10^{7}$。
分析：
已知$$a^b\%p=(a\%p)^{\phi(p) + b \% \phi(p)} \% p$$
那么$$f(p)=(2 \% p)^{2^{2^{2^{…^2}}}\%\phi(p)+\phi(p)}\% p$$
即$$f(p)=(2\%p)^{f(\phi(p))+\phi(p)} \% p$$
根据 $n为奇数，\phi(2n)=\phi(n)，n为偶数，\phi(2n)=2\phi(n)$，总是可以转化成一半处理，在$O(logp)$内变为$1$，$f(1)=0$，递归截止。
加上因式分解求欧拉函数总体时间复杂度$O(logp\sqrt p)$。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| > File Name: 3884.cpp > Author: jiangyuzhu > Mail: 834138558@qq.com > Created Time: 2016/8/30 19:08:42 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<set> #include<map> #include<algorithm> using namespace std; typedef long long ll; int euler(int n) { int res = n; for(int i = 2; i * i <= n; i++){ if(n % i == 0){ res = res / i * (i - 1); while(n % i == 0) n /= i; } } if(n != 1) res = res / n * (n - 1); return res; } int quick_pow(int b, int a, int p) { ll res = 1; for(; a; a >>= 1, b = b * 1ll * b % p){ if(a & 1) res = res * 1ll * b % p; } return res; } int a2; int dfs(int p) { if(p == 1) return 0; int np = euler(p); return quick_pow(a2, dfs(np) + np, p); } int main (void) { int T;scanf("%d", &T); while(T--){ int p;scanf("%d", &p); a2 = 2 % p; printf("%d\n", dfs(p)); } return 0; }
|
