$ gcd(a,p) $=1时扩展欧拉定理依然适用
by zzy2333 @ 2019-10-07 11:03:12
@[zzy2333](/space/show?uid=118058) 如果 $\gcd(a,p)=1$ 的话，$a^b\mod p$ 不是等价于 $a^{b\mod \phi(p)}$ 吗，指数 $b$ 不需要额外加 $\phi(p)$ 吧？
by strawberrry @ 2019-10-07 11:05:27
@[strawberrry](/space/show?uid=93110) 对，但是加了$\phi(p) $也没有问题
by zzy2333 @ 2019-10-07 11:06:52
@[zzy2333](/space/show?uid=118058) 不加也没问题吧？我的疑惑是，按我代码的写法，如果不加就会 WA，加了就能 AC
by strawberrry @ 2019-10-07 11:08:17
感觉是我写法问题，CF 906D 加了这句判断 $\gcd(a,p)$ 的也 WA 了，不加也能 AC。
我再仔细找找问题，感谢 @[zzy2333](/space/show?uid=118058) 大佬提示。
by strawberrry @ 2019-10-07 11:19:14