玩转模运算和模取幂运算

直接插入主题:

1.当a,b,c 都比较小的时候，可以使用赤裸裸的暴力
伪代码:
v:=1;
for i := 1 to b begin
v:=v*a;
v:=v mod c;
end

这也是我们在第一次遇到这种问题的时候首先能想到的.

2.a,b,c都比较大的时候
这里需要考虑c的大小了，假设c*c<2^64吧(再大就只能再做特殊处理了)
b比较大的话使用1的方法显然时间上是承受不了的，所以可以利用所谓的二分法.
b=b0+b1*2^1+b2*2^2+...+bn*2^n
显然a^b可以变成若干项的乘积
伪代码:
v:=1;
while b<>0 do begin
if (b and 1= 1) do begin v:=v*a;v:=v mod c;end
a:=a*a;
a:=a mod c;
b:=b shr 1;
end
3.如果c很大，那么需要使用到模拟乘法来避免溢出,当然如果c已经大到10^100,那么只能用高精了..这里只能处理最多c=2^64-1的情况吧

伪代码:
int mul(int a,int b,int c)
{
int ret=0,tmp=a%c;
while(b)
{
   if(b&0x1)if((ret+=tmp)>=c)ret-=c;
   if((tmp<<=1)>=c)tmp-=c;
   b>>=1;
}
return ret;
}

4.如果b已经爆大，那么使用logb的算法显然已经力不从心
于是可以考虑利用循环节的方法来求解
如果c比较小，那么可以直接暴力得到循环节
对于a^b mod c

a.if gcd(a,c)==1
那么可以知道它的循环节开始位置必然是1,而且循环节长既为它的欧拉函数的因子
因为有a^p mod c= 1
所以p可以看成是周期
b.if gcd(a,c)!=1 那么循环节是否一定不从1开始呢？答案是否定的
why?
因为假设存在某个L'使
a mod c = a^(1+L') mod c= a* a^L' mod c
那么可以解到许多满足条件的B',使a*B' = a mod c (mod c)
解的个数就是gcd(a,c)，然后如果能找到a^L' = B' (mod c)
那么其开始位置依然可以是1
当然其他大多数情况下循环节开始位置都不是1

好了下面用暴力得到了循环节开始位置spos,和循环节长len

下面用到公式
就可以在比较快的时间内求解了

如果c非常大那怎么办？

可以利用抽屉原理+baby-step,giant-step扩展应该可以得到循环节的长度，接下来循环节的开始位置我还没有想到比较好的算法，暂时只能暴力了-_-,谁有思路请留言谢谢~