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


题目链接: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)\) 的,由于常数问题会死,大力转移即可。

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3884 上帝与集合的正确用法


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,