WA on #3 #20 警钟蕨蕨
查看原帖
WA on #3 #20 警钟蕨蕨
1066579
XP3301_Pipi楼主2024/7/17 22:38

预处理可能出现的欧拉函数值时,当出现 11 时,要再加入一个 11 保证正确性。
否则,当 Ai=0A_i=0 时会出错。这里给出一个详细说明。
递归过程中,当 ϕ(p)=1\phi(p)=1 时,也就是在计算 fcX mod 1fc^{X} \bmod 1 会出现两种情况:
1.X=Ai=0X=A_i=0,此时满足扩展欧拉定理中的 X<ϕ(p)X<\phi(p),则有 cX≡cX mod ϕ(p)≡1(modp)c^{X}\equiv c^{X \bmod \phi(p)} \equiv 1 \pmod{p}。
2.X=ccc…X=c^{c^{c\dots}},对 XX 进行递归可得 Xcc…≡X0≡1(modp)X^{c^{c\dots}}\equiv X^0 \equiv 1 \pmod{p},此时满足扩展欧拉定理中的 X≥ϕ(p)X\geq \phi(p),则有 cX≡cX mod ϕ(p)+ϕ(p)≡c1≡c(modp)c^{X}\equiv c^{X\bmod \phi(p)+\phi(p)}\equiv c^1 \equiv c\pmod{p}。
如果在这时直接返回,就会出错。解决方法就是对 XX 再递归一层,就可以实现对两种情况的充分讨论。

2024/7/17 22:38
加载中...