相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3884
官方题解:http://blog.csdn.net/popoqqq/article/details/43951401
解题报告
根据欧拉定理有:$a^x \equiv a^{x \% \varphi (p) + \varphi (p)} \mod p$
设$f(p)=2^{2^{2 \cdots }} \mod p$
那么有$f(p) = 2^{f(\varphi(p)) + \varphi(p)} \mod p$
如果$p$是偶数,则$\varphi(p) \le \frac{p}{2}$
如果$p$是奇数,那么$\varphi(p)$一定是偶数
也就是说每进行两次$\varphi$操作,$p$至少除$2$
所以只会递归进行$\log p$次
总时间复杂度:$O(T\sqrt{p} \log p)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { ret = ret * 10 + c - '0'; c = getchar(); } return ret * f; } inline int get_phi(int x) { int ret = x; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { ret = ret / i * (i - 1); while (x % i == 0) { x /= i; } } } return x == 1? ret: ret / x * (x - 1); } inline int Pow(int w, int t, int MOD) { int ret = 1; for (; t; t >>= 1, w = (LL)w * w % MOD) { if (t & 1) { ret = (LL)ret * w % MOD; } } return ret; } inline int f(int p) { if (p == 1) { return 0; } else { int phi = get_phi(p); return Pow(2, f(phi) + phi , p); } } int main() { for (int i = read(); i; --i) { printf("%d\n", f(read())); } return 0; }