[BZOJ3884] 上帝与集合的正确用法

题目

题目链接.
2^{2^{2^{...}}}\ mod\ p 的值。
 

思路

首先有 a^b \equiv a^{b\ mod\ \phi(p)}\ (Mod \ p) \ \ gcd(a, p) = 1. 所以对于第一层指数,我们可以模 \phi(p). 第二层指数我们可以模 \phi(\phi(p)).以此类推,最终要模 \phi(\phi(....\phi(p))).而 phi(p) < p.也就是说这个序列是严格递减的,最终会有 \phi(\phi(....\phi(p))) = 1.这也就是递归的边界。那么对于 a,p不互质的情况有 A^B mod C = A ^ {B mod \phi(C) + \phi(C)} mod C \ \ \ B > \phi(C).这样就可以解决。
所以可以一步一步递归,直到欧拉函数值为 1 ,再一层一层返回去。
 

代码

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注