【Bzoj3884】上帝与集合的正确用法

题目大意

求2222222...mod　p的值。$求2^{2^{2^{2^{2^{2^{2^{...}}}}}}}mod　p的值。$

分析

po姐的题目诶！！$po姐的题目诶！！$ 大意就是上面那样，看上去+∞个2根本不可做，不过有欧拉定理xa≡xa　mod　φ(p)+φ(p)　(mod　p)。$大意就是上面那样，看上去+∞个2根本不可做，不过有欧拉定理x^a≡x^{a　mod　φ(p)+φ(p)}　(mod　p)。$ 那么我们有f(n)=2222222...(mod　n)$那么我们有f(n)=2^{2^{2^{2^{2^{2^{2^{...}}}}}}}(mod　n)$ =2(222222...　mod　φ(n))+φ(n)　(mod　n)$=2^{(2^{2^{2^{2^{2^{2^{...}}}}}}　mod　φ(n))+φ(n)}　(mod　n)$ =2f(φ(n))+φ(n)　(mod　n)$=2^{f(φ(n))+φ(n)}　(mod　n)$ 递归做下去即可，当n==1，返回0(任何数mod　1等于0)。$递归做下去即可，当n==1，返回0(任何数mod　1等于0)。$ 欧拉函数建议直接算，递推不知道会不会TLE。$欧拉函数建议直接算，递推不知道会不会TLE。$