快速幂取模，是指求(a^n)%m , a和n都非常的大，如果直接计算a^n可能直接溢出，在这种情况下取模，需要用到同余定理的一些推论。
关于同余定理，可以看这里，注意幂运算部分，“幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)“ ，若a、b取m同余，则a^n、b^n关于m同余，注意a与a%m是同余的，所以把b替换为a%m，得a^n ≡ (a%m)^n (mod m)，即(a^n)%m=((a%m)^n)%m快速幂取模就是运用了这个公式，把a^n拆开运算。
- 先来看直接运用这个公式。
直接运用就是直接把aaaa……拆开，拆成(a%m)(a%m)(a%m)(a%m)……然后再取模，上代码
long long solve(int a, int n, int m) {求a^n的模
long long ans = 1;
a = a%m;//先取一次模把数变小，a%m%m=a%m
for (int i = 1; i <= n; i++) {
ans = ans*(a%m);
}
return ans%m;
}
注意到这里展开就变成了(a%m)(a%m)(a%m)*(a%m)，值得警惕的是，当m和n比较大，还是有很大的可能会溢出，因为要连乘法n次，于是有了第二种写法。
long long solve(int a, int n, int m) {求a^n的模
long long ans = 1;
a = a%m;//先取一次模把数变小，a%m%m=a%m
for (int i = 1; i <= n; i++) {
ans = (ans*a)%m;
}
return ans%m;
}
只改动了代码的第5行，改动后展开变成了((((a%m)a)%ma)%ma)%m……稍微推一下就可以推出这个式子和上面的(a%m)(a%m)(a%m)(a%m)……是同余的，那这样写有什么好处呢，好处就是降低了溢出的可能性，每次*a后都要%m,相当于每次都把结果控制在了0~m-1的范围内，大大减小了溢出的可能性。所以这种写法是比第一种要更安全的。
但是这两种方法都有一个问题，那就是，时间复杂度为O(N)，每次都要乘啊，这么写代码，难道计算机不会痛嘛！于是就有了第二种算法，快速幂取模。
- 快速幂取模
快速幂取模，是一种二分的思想，怎么说呢，举个栗子吧，6^16==36^8==(66)^8，怎么运用这个来快速取模呢，(6^16)%m=((66)^8)%m={[(66)^4][(6*6)^4]}%m,看起来好不方便，那我们直接上代码吧
ps：如果是6^17次方呢？怎么二分，答案是，我们先提出来一个6变成(66^16)%m==((6%m)(6^16%m))%m，这样就可以正常运算了。
long long solve(long long a, long long n, long long m)
{
long long ans = 1;
a = a % mode;
while (n > 0) {
if (n % 2 == 1) //判断是否是奇数，也可以使用&符合判断是否为奇数
ans = (ans * a) % m;
a = (a * a) % m;// 不断的两两合并再取模
n /= 2;//这里可以使用位运算 n>>=1 来除以2，使用位操作运算速度更快。
}
return ans%m;
让我们随便带个数进去看看~假若a是6，n是16，即求(6^16)%，在这个算法中会怎么走呢？
n=16; a=6%m; 进入循环: a=( (6%m) * (6%m) )%m;// 即(6*6)%m 运用了公式(a*b)≡(a%m)*(b%m)(mod m),这个公式是因为a与a%m同余，b与b%m同余，所以a*b与a%m*b%m同余; n=8; a=( (6*6)%m * (6*6)%m )%m//即(6*6*6*6)%m n=4; a=( (6*6*6*6)%m * (6*6*6*6)%m )%m//即(6^8)%m; n=2; a=(6^16)%m; n=1; 判断n是奇数，所以 ans=(6^16)%m; 后面对a的赋值已经没有比较管了，因为n/2=0会直接跳出循环，得到ans即为答案。
如果n是奇数会如何？假若a=6,n=17
n=17; a=6%m; 进入循环: 判断n(17)是奇数 ans=6%m; a=( (6%m) * (6%m) )%m;// 即(6*6)%m 运用了公式(a*b)≡(a%m)*(b%m)(mod m); n=8; a=( (6*6)%m * (6*6)%m )%m//即(6*6*6*6)%m n=4; …… 可以看到，奇数的时候，程序先取出了一个6，然后剩下6^16正常处理 最后n=1时，ans = (ans * a) % m;会把第一个取出来的值也乘上去, 得到ans=( (6%m) * ((6^16)%m) )%m = (6^17)%m;即为所求
例题：
这题不仅用到了同余定理在乘法方面的推论，还用到了在加法方面的推论，堪称模板题。题解自行百度。