Java教程

快速幂学习笔记

本文主要是介绍快速幂学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

快速幂很有用哦!!

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

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

什么是快速幂

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

这篇关于快速幂学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!