预处理会出现的欧拉函数序列时,当 ϕ(x)=1 时,要在后面再加一个 1。
否则,当 Ai=0 时会出错。
假设 ϕ(p)=1,ccAi≡ccAimod1+1≡c(modp)。
当程序发现 ϕ(p)=1 时,可能会忽视后面的 +1,导致计算出的结果为 c0,也就是 1。
原因就是,当 ϕ(p)=1 时,指数上的 c 如果还有一大串,递归返回值一定是 0,此时满足扩展欧拉定理中的 ccc…<ϕ(p);
若指数上的 c 上面只有一个 Ai,cAi=1,此时满足扩展欧拉定理的 cAi≥ϕ(p),需要加 ϕ(p)。
归根结底,就是程序无法区分指数的 0 到底是 Ai 还是 ccc…,从而无法正确运用扩展欧拉定理。
所以需要在 ϕ(p)=1 时多计算一步。