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

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

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