前言

快速幂很有用哦！！

目前本文还没有例题，因为没有什么好题啊。

以后看一下能不能找一些题目。

什么是快速幂

幂，也就是次幂，可以理解为计算 \(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