预处理可能出现的欧拉函数值时,当出现 1 时,要再加入一个 1 保证正确性。
否则,当 Ai=0 时会出错。这里给出一个详细说明。
递归过程中,当 ϕ(p)=1 时,会出现两种情况:
设此时的目标式子为 cXmodp。
1.X=Ai=0,此时满足扩展欧拉定理中的 X<ϕ(p),则有 cX≡cXmodϕ(p)≡1(modp)。
2.X=ccc⋯,对 X 进行递归可得Xcc⋯≡X0(modϕ(p)),此时满足扩展欧拉定理中的X≥ϕ(p)
,则有cX≡cX mod ϕ(p)+ϕ(p)≡c1≡c(modp)。
如果在这时直接返回 c,就会出错。
解决方法就是对 X 再递归一层,就可以实现对两种情况的充分讨论。