关于次幂取模
需要处理的是a^b mod p。
如果(a,p)=1,我们直接上欧拉定理就好了。
如果(a,p)<>1,我们求出gys=(a,p)。然后我们递归处理就好了。
如下:
递归处理即可。
复杂度很诡异。但是看上去比较小。题解说复杂度一般在线性筛上。
需要处理的是a^b mod p。
如果(a,p)=1,我们直接上欧拉定理就好了。
如果(a,p)<>1,我们求出gys=(a,p)。然后我们递归处理就好了。
如下:
递归处理即可。
复杂度很诡异。但是看上去比较小。题解说复杂度一般在线性筛上。