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

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

2024/7/17 21:43
加载中...