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


题意

求 \(2^{2^{2^{2^{\cdots }}}}\; mod\; p\) 的结果。

分析

利用拓展欧拉定理:\(a^b\equiv a^{\text{min}(b,b\; mod\; \varphi(m)+\varphi(m))} (mod \;m)\)  ,可以得到:

\(2^{2^{2^{2^{\cdots }}}}\equiv 2^{(2^{2^{2^{2^{\cdots }}}} \; mod \; \varphi(p) + \varphi(p) )}(mod\; p)\) ;
而 \(2^{2^{2^{2^{\cdots }}}} \equiv 2^{(2^{2^{2^{2^{\cdots }}}} \; mod \; \varphi(\varphi(p)) + \varphi(\varphi(p)) )}(mod\; \varphi)\) 。
显然这是一个不断变成 \(2^{2^{2^{2^{\cdots }}}}\; mod\; \varphi(\varphi(\cdots p))\) 子问题的过程。
经过不断的 \( \varphi(\varphi(\cdots p))\) 迭代,最终一定会变成 \(1\) ,而显然,\(2^{2^{2^{2^{\cdots }}}}\; mod\; 1=0\) ,此时可以开始回溯。
考虑需要进行多少次迭代。
  • 如果 \(p\) 是奇数,那么 \(\varphi(p)\) 一定为偶数;
  • 如果 \(p\) 是偶数,那么\(\varphi(p)\) 一定满足 \(\varphi(p)\le \frac{p}{2}\) 。
于是可以得到 \(\varphi(\varphi(p))\le \frac{p}{2}\) ,所以递归次数级别是 \(log_2n\) 的。
时间复杂度为 \(O(Tlog_2p)\) 。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 67,589

Categories

Archive

Comments