快速幂与快速幂求模

普通的暴力求法

int mi(int a,int b)
{int num=1;int i;for(i=0;i<b;i++){num=num*a;}return num;
}

这种暴力求法的时间复杂度是O(n)，为了降低时间复杂度，我们引用快速幂，它的时间复杂度缩短到O(logn)。

快速幂的核心

我认为快速幂之所以快，主要是运用到了位运算。
对于位运算，我们举个例子
比如：2^13
13的二进制为1101，那我们可以得到1* 2^0+0 * 2 ^1+1* 2 ^2+1* 2 ^3=13
带回去可得：2 ^(1* 2 ^0+0* 2 ^1+1* 2 ^2+1 * 2 ^3)
得出结果为2 ^(1*2 ^ 0)*2 ^(1 *2 ^ 2)*2 ^(1 *2 ^ 3);
由此我们可以总结出，对于幂，我们可以将其化为二进制一位一位读取，碰到0，则不做操作，碰到1我们就进行累乘；
用代码表示

int mi(int a,int b){int num = 1;while(b){if(b & 1) num=num*a;a=a*a；b >>= 1;}return num;
}

我们进行实际的模拟

快速幂取模

对于快速幂的模运算其实和快速幂大部分相同，就是在快速幂的同时进去取模，所以我们只要根据公式对原代码进行加工便可得
模运算公式：(a*b) mod c = ((a mod c) * (b mod c)) mod c；
(a ^ b) mod c = (a mod c) ^ b mod c；
主要看第二个定理；

int mi(int a,int b,int m)
{int num = 1;while(b){if(b & 1) num=num*a%m;a=a*a%m；b >>= 1;}return num;
}

因为我们对a ^ n进行二进制拆分，所以这里的模运算，其实是运用到了分配率的一个用法。