admin管理员组文章数量:1033514
【倍增思想】须知少年凌云志,曾许人间第一流
本篇博客给大家带来的是倍增思想的题目讲解, 利用此思想解决快速幂 和 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. 计算过程,存在除法,取模将会造成结果错误,此时需要求逆元,此规则后续有遇到再补充.
代码语言：javascript代码运行次数：0运行复制三. 代码实现
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 …
代码语言：javascript代码运行次数：0运行复制二. 代码实现
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;
}
}总结, 倍增思想实现快速幂的本质就是二进制边枚举边倍增,再加上判断.这种实现方式的代码非常好写,是赛场上的首选.
本篇博客到这里就结束啦, 感谢观看 ❤❤❤
【倍增思想】须知少年凌云志,曾许人间第一流
本篇博客给大家带来的是倍增思想的题目讲解, 利用此思想解决快速幂 和 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. 计算过程,存在除法,取模将会造成结果错误,此时需要求逆元,此规则后续有遇到再补充.
代码语言：javascript代码运行次数：0运行复制三. 代码实现
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 …
代码语言：javascript代码运行次数：0运行复制二. 代码实现
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; } }总结, 倍增思想实现快速幂的本质就是二进制边枚举边倍增,再加上判断.这种实现方式的代码非常好写,是赛场上的首选.
本篇博客到这里就结束啦, 感谢观看 ❤❤❤
本文标签： 倍增思想须知少年凌云志曾许人间第一流
版权声明：本文标题：【倍增思想】须知少年凌云志,曾许人间第一流 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748050499a2246931.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论