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