多项式是否符合拓展欧拉定理？
查看原帖
多项式是否符合拓展欧拉定理？
239163
MarchKid_Joe楼主2022/7/25 11:28

很玄学，我用高精暴力对指数取模k mod 998244353k\bmod998244353，然后跑快速幂，结果ACAC了，但让指数kk对φ(998244353)\varphi(998244353)即(998244352)(998244352)取模后再加上(998244352)(998244352)却WrongWrong掉了。

ab≡{ab  mod φ(m)gcd(a,m)=1abgcd(a,m)≠1,b<φ(m),( mod m)a(b  mod φ(m))+φ(m)gcd(a,m)≠1,b⩾φ(m)a^b\equiv \begin{cases} a^{b\,\bmod\varphi(m)} &gcd(a,m)=1\\ a^b &gcd(a,m)\not=1,b<\varphi(m),(\bmod m)\\ a^{(b\,\bmod\varphi(m))+\varphi(m)} &gcd(a,m)\not=1,b\geqslant\varphi(m) \end{cases} 
k%=Mod;



k%=phi;
k+=phi;
2022/7/25 11:28