思路:
使用扩展欧拉定理计算幂塔, 即:
$\varphi(m)$的收敛速度是$\log m$级别的, 所以直接递归计算即可.
收敛速度的证明
引理: 对于$n>2$, $\varphi(n)$均为偶数.
可以使用更相减损法证明, 由于$(x,n)=(n-x,n)$, 所以这两个数成对互质或不互质
于是$n$有质因子2, 每次求$\varphi$都会至少除2, 所以收敛速度是$\log m$级别的.
分类讨论处理起来可能会稍微有点棘手. 代码中修改了一下快速幂, 当中间值比$m$大时则返回ret+m.
代码:
1 |
|