BZOJ 3884 上帝与集合的正确用法

发布于 2018-01-11  146 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3884

题意:求 \(2^{2^{2^{...}}}\ mod\ p\)


记 \(2^{2^{2^{...}}}\ mod\ p\),显然有\(f_1=0\)。

显然\(2^{2^{2^{...}}} \) 远大于 \(\varphi (p)\) ,可以直接应用扩展欧拉定理。

即 \(f_p=2^{f_{\varphi (p)}+\varphi (p) }\ mod p \ \)

直接递推是\(O(p)\) 的,由于常数问题会死,大力转移即可。

数学公式好像几乎全挂了... 感性理解吧

 


一个非常弱的准退役OIER