快速取模运算

1.求a^n%Mod 的运算

先研究一个实例：3^45的乘法原理：

45（10）=101101（2）

45=2^5+2^3+2^2+1=32+8+4+1;运算规模由O（n)变成O(log(n))。

3^45=3^32*3^8*3^4*3;

而由公式：a*b%c=(a%c)*(b%c)

证明如下：

不妨令a=k1*c+x1,b=k_2*c+x₂;

那么a*b=(k1*c+x1)*(k_2*c+x₂)%c=x1*x2%c;

而(a%c)*(b%c)=((k1*c+x1)%c)*((k_2*c+x₂)%c)=x1*x2%c;

故得证。

可以写出如下代码：

 1 const int MOD = 10007;
 2 int PowMod(int a, int n)//a^n%MOD
 3 {
 4 int ret = 1; 
 5 while(n) 
 6 { 
 7 if(n & 1) ret = ret * a % MOD;
 8 a = a * a % MOD; 
 9 n >>= 1;//相当于对数据每次除以2并取商n/=2;
10 }
11 return ret;
12 }

这样就可以把模快速求出来了。