【倍增思想】须知少年凌云志,曾许人间第一流 - 彻底解决快速幂

用户11369350

发布于 2025-04-01 00:57:10

7700

代码可运行

文章被收录于专栏：Java,后端开发,网站开发,数据结构,算法分析.Java,后端开发,网站开发,数据结构,算法分析.

运行总次数：0

代码可运行

本篇博客给大家带来的是倍增思想的题目讲解, 利用此思想解决快速幂和 64位整数乘法非常好用.

1. 快速幂

题目链接: P1226 【模板】快速幂

题目内容: 题目描述给你三个整数 a,b,p，求 a^b mod p。

输入格式输入只有一行三个整数，分别代表 a,b,p。

输出格式输出一行一个字符串 a^b mod p=s，其中 a,b,p 分别为题目给定的值， s 为运算结果。

输入输出样例

一. 倍增思想的原理

a^1 = a a ^ 2 = a * a a ^ 4 = a^2 * a^2 a ^ 8 = a^4 * a^4 … 上述枚举的都是偶数次的,如果要求某个数的奇数次,该怎么求? 比如a^11 11的二进制表示为1011, 由二进制求十进制11 = 1*2 ^ 3 + 0 * 2 ^ 2 + 1 * 2 ^ 1 + 1 * 2^0; 发现二进制与倍增过程有对应关系:

综上, 我们可以枚举b的二进制, 枚举一次,判断当前位是否为1,是的话就将倍增数a加入到结果中, 不是1的话就继续枚举,直到枚举完 b 的所有二进制位.

二. 没有一种数据类型能够存下a^b的极端值,该如何解决这种问题? 通常题目会给出具体的取模数字, 需要注意以下三种取模运算规则

1. 计算过程只有加法和乘法是,取模可以放在任意位置 (a * b * c * d) % p = (a%p * b%p * c%p * d%p);

2. 计算过程存在减法,对结果取模可能出现负数, 如果需要化负为正,则通过"模加模"的方式来转化. 比如:(a-b)%p,将此式变为: [((a-b)%p)%p)+p]%p

3. 计算过程,存在除法,取模将会造成结果错误,此时需要求逆元,此规则后续有遇到再补充.

三. 代码实现

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong(),b = sc.nextLong(),p = sc.nextLong();
		long ret = qpow(a,b,p);
		System.out.println(a+"^"+b+" mod "+p+"="+ret);
	}
	public static long qpow(long a,long b,long p) {
		long ret = 1;//保存结果
		while(b > 0) {
			if((b&1) == 1) {
				ret = ret*a%p;
			}
			a = a*a%p;
			b >>= 1;//b右移一位.
		}
		return ret;
	}
}

2. 64位整数乘法

题目链接:

链接: P10446 64位整数乘法

题目内容: 求 a 乘 b 对 p 取模的值。

输入格式第一行输入整数 a，第二行输入整数 b，第三行输入整数 p。

输出格式输出一个整数，表示 a*b mod p 的值。

一. 分析题意

a × b = b个a相加 a = a 2a = a + a 4a = 2a + 2a 8a = 4a + 4a 16a = 8a + 8a …

二. 代码实现

import java.util.Scanner;

//64位整数乘法
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong(),b = sc.nextLong(),p = sc.nextLong();
		System.out.println(mul(a,b,p));
	}
	public static long mul(long a,long b,long p) {
		long ret = 0;
		while(b > 0) {
			if((b&1) == 1) {
				ret = (ret+a)%p;
			}
			a = (a+a)%p;
			b >>= 1;
		}
		return ret;
	}
}