撰写目录
这是一个无论在OI还是在程序员编程中都十分重要但也十分简单易懂的算法！在此一个蒟蒻简单的讲一下这个算法。
从字面上看，KSM是什么（kuai su mi）？这个算法有什么用？ 快速幂，肯定是用来进行幂运算的，而且比朴素算法更高效。
先来看一个朴素算法
例如：求x的n次方（当然这里我们不考虑高精度问题）。
long long ans=1; for(int i=1;i<=n;i++) ans=(ans*x)%Mod;
显然这个算法最清楚明白，不就是定义吗？可是他的复杂度是O（n）的，如果你要算一个排列组合之类的题目，需要进行大量幂运算，那么这个复杂的太可怕了，我们必须想个办法优化他！
快速幂算法——反复平方法
我们思考这样一个问题。求2的32次方你可以怎么计算？ 当然你可以像上面的可爱的朴素算法一样计算32遍，看起来没什么问题。但是：你还可以有另一种算法：
- 给2平方，得到2^2=4.
- 给4平方，得到2^4=16.
- 给16平方，得到2^8=256.
- 给256平方，得到2^16=65536.
- 给65536平方，得到2^32=4294967296
如上，你仅仅需要5次运算，就轻松地求出了2^32，真实太棒了。在这样一个小的指数下，或许快速幂的优势并不明显（其实已经很明显了，暑假剩32天和剩5天差别大不大啊？）
所以，算法就是这样，我们看一下代码：
依然是求x的n次方，依然不考虑高精度。我不会
long long ans;
const long long Mod=1e9+7;
void KSM(long long x,long long n){ //求x的n次方
ans=1;
while(n){
if(n&1) //判断n的最后一位是否是1
ans=(ans*x)%Mod;
n>>=1; //舍去n的最后一位
x=(x*x)%Mod; //给x平方
}
return ans%Mod;
}
PS：这里我说的哪一位什么的都是二进制。
如此一来，我们只需要计算a、a^2、a^4、a^8……的值（这个序列中的项不一定都存在，由n的二进制对应位为0/1决定）并把它们乘起来即可完成整个幂运算。借助位运算的操作，我们可以很方便地实现这一算法，其复杂度为O(logn)。 这个时间复杂度的优化是非常可观的。
快速幂的拓展
快速幂还有一个拓展，叫做矩阵快速幂，本质上讲差别不大，只是加入了矩阵运算而已，我想你们一定都会（其实是因为我不会），所以我推荐一个嘴子的文章供你们学习！ https://leirui.home.blog/2019/07/17/%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82/
2019.10.21 Update：补上矩阵快速幂的坑，比上面那个嘴子写的好多了！！！
https://www.tongli.ink/%e7%9f%a9%e9%98%b5%e5%8a%a0%e9%80%9f
wpDiscuz