前言
快速幂很有用哦！！
目前本文还没有例题，因为没有什么好题啊。
以后看一下能不能找一些题目。
什么是快速幂
幂，也就是次幂，可以理解为计算 \(x^y\)。
由于 \(x^y\) 会特别大，所以一般都是求 \(x^y \bmod p\)。
朴素的做法如下：
#define LL long long
LL slow_pow(int x, int y, int p)
{
//由于精度问题，开 long long 明显更保险。
LL mul = 1;
for (int i = 1; i <= y; i++) mul = (mul * x) % p;
return mul;
}
这样做，时间复杂度是 \(O(y)\)，太慢了。
快速幂可以巧妙地在 \(O(\log y)\) 的时间内计算幂。
哪怕 \(y\) 处于 long long 级别（\(y \le 10^{18}\)），计算速度都为常数。
快速幂实现方式有很多，下面讲解常见的两种实现方式：二进制 与 递归分治。
实现方法
方法 01
这个办法围绕一条明显成立的等式展开：\(x^{a+b} = x^a \cdot x^b\)。
实际上，如果 \(y = 2^n\) （\(n\) 是自然数），计算 \(x^y \bmod p\) 的时间复杂度就是 \(O(\log y)\)。
因为可以利用倍增的思想，先算出 \(x^1\)，然后得到 \(x^2 = x^1 \cdot x^1\)，进而得到 \(x^4 = x^2 \cdot x^2\)，以此类推。
那么，我们可不可以将 \(y\) 分解成若干个 \(2^n\) 姓形式的数呢？
当然可以！二进制拆分！
举个例子，\(x = 2, y = 10\)。
我们把 \(y\) 进行二进制拆分，这里 \((10)_{10} = (1010)_2\)。
所以 \(x^{10} = x^2 \cdot x^8\)。
我们可以用变量 \(\texttt{base}\) 记录当前 \(x^{\texttt{二次幂}}\) 的值，按照上述的倍增思想，每次自乘即可。
一边计算二进制一边计算答案，每逢二进制的那一位的值为 \(1\)，\(\texttt{ans}\) 乘上 \(\texttt{base}\)。
大致原理就是这样，直接给出 C++ 代码。
#define LL long long
int fast_pow(int x, int y, int p) //求 x^y mod p
//也有以 ksm 命名的，即快速幂的首字母。
{
LL ans = 1, base = x;
while (y) //等同于： while(y != 0)
{
//此处 y&1 是位运算常数优化，等同于 if (y % 2 == 1)
if (y & 1) ans = (ans * base) % p;
base = (bse * base) % p; //自乘，与上述原理相同。
y >>= 1; //同样是位运算常数优化，等同于 y /= 2;
}
return (int)(ans);
}
挺好理解的吧，给出精简一些的代码，考试时就打下面这份，速度快一些。
#define LL long long
int ksm(int x, int y, int p){
LL a=1, t=x;
while(y){
if(y&1) a=(a*t)%p;
t=(t*t)%p;
y>>=1;
}
return (int)a;
}
接下来，再看第二种更好理解的方法：递归。
方法 02
分两种情况考虑。
若 \(y\) 是偶数，\(x^y = x^{y \div2} \times x^{y \div2}\)；
若 \(y\) 是奇数，\(x^y = x^{y \div2} \times x^{y \div2} \color{red}{\space \times\space x}\)。
利用递归求出 \(x^{y \div 2}\)，然后按照两种情况计算出答案就完事了。
终止条件是 \(y = 1\)，答案就是 \(x \bmod p\)。
代码如下：
#define LL long long
int fast_pow(int x, int y, int p)
{
if (y == 1) return x % p; //终止条件
//下面 y >> 1 是位运算，等同于：y / 2
LL ans = fast_pow(x, y >> 1, p);
if (y % 2 == 0) //与方法01相同，可以用位运算压，这里没有使用。
{
ans = (ans * ans) % p;
return (int)(ans);
}
else
{
ans = (ans * ans) % p;
ans = (ans * x) % p; //这两句话等同于 ans = ans * ans * x 这样乘一次模一次，防止数据溢出。
return int(ans);
}
}
注意到两种情况都包含了语句：
ans = (ans * ans) % p;
以及这条语句：
return (int)(ans);
所以，我们可以简单地缩短码量，最终精简代码如下：
#define LL long long
int ksm(int x, int y, int p)
{
if(y==1) return x%p;
LL t=ksm(x, y>>1, p);
t=(t*t)%p;
if(y&1)t=(t*x)%p;
return (int)t;
}
首发：2022-05-29 15:46:56
标签：return,int,LL,long,学习,base,笔记,ans,快速 From： https://www.cnblogs.com/liangbowen/p/16622880.html