Java语言实现快速幂取模算法详解
作者:QuinnNorris 发布时间:2022-06-08 13:18:51
快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的,在朴素的方法中我们计算一个数比如5^1003%31是非常消耗我们的计算资源的,在整个计算过程中最麻烦的就是我们的5^1003这个过程
缺点1:在我们在之后计算指数的过程中,计算的数字不都拿得增大,非常的占用我们的计算资源(主要是时间,还有空间)
缺点2:我们计算的中间过程数字大的恐怖,我们现有的计算机是没有办法记录这么长的数据的,所以说我们必须要想一个更加高效的方法来解决这个问题
当我们计算AB%C的时候,最便捷的方法就是调用Math函数中的pow方法,但是有时A的B次方数字过大,即使是双精度的double也会溢出,这个时候为了得到AB%C的结果,我们会选择使用快速幂取模算法,简单快速的得到我们想要的结果。
为了防止数字溢出并且降低复杂度,我们需要用到下面的公式:
ab mod c = (a mod c)b mod c
这个公式的意思就是:积的取余等于取余的积的取余。很容易看出来这个公式是具有传递性的,这样我们可以通过不断的取余让a越来越小,防止出现溢出的情况。
理论上,有了这个公式我们就可以写代码了,通过不断的对a进行取模保证结果不会溢出,这确实能计算出较大次方的幂的模,但是这种方法的复杂度仍旧是O(N),并不快速。
为了更快速的计算出幂的模,我们还要依赖下面这个公式:
ab mod c = (a2)b/2 mod c , b为偶数
ab mod c = ((a2)b/2·a) mod c , b为奇数
这个公式很简单,原理就是不断的用a的平方来代替b,将b替换为原来的一半。因为我们通过第一个公式知道了一个数的模的相同次方的模相同(这句话说的有点绕,就是公式一的意思)。那么我们用a*a%c的结果来代替a效果是一样的。
所以根据上述的公式,我们得到复杂度O(logN)这样的计算快速幂的方法:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
int res = 1;
a %= c;
for (; b != 0; b /= 2) {
if (b % 2 == 1)
res = (res * a) % c;
a = (a * a) % c;
}
System.out.println(res);
}
}
这个算法大概如此,第一步先a%=c是为了将a缩小一些,防止在for中第一次进行a*a的时候数字溢出。在for循环中,如果是b为奇数则令res=res*a,直接先将a乘到结果中去,最后做处理,又是为了防止数字溢出直接将res*a的结果mod c操作。这个for循环中,早晚有一天b会等于1,进入if分支,最后将res的值计算完毕mod c退出for循环,的到最后的结果。
来源:http://blog.csdn.net/quinnnorris/article/details/77587096
猜你喜欢
- Java虚拟机把描述类的数据从Class文件加载到内存,并对数据进行校验、转换解析和初始化,最终形成可以被虚拟机直接使用的Java类型,这个
- 参考视频:https://www.bilibili.com/video/BV1Bq4y1Q7GZ?p=4通过视频的学习和自身的理解整理出的笔
- iOS定位 - 普通定位(没有地图) - 反地理编码(得到具体位置),下面通过代码给大家详解,代码如下:#import <CoreLo
- 定义:用于顺序访问集合对象的元素,不需要知道集合对象的底层表示。特点: 1、它支持以不同的方式遍历一个
- 本文实例为大家分享了java实现简单石头剪刀布游戏的具体代码,供大家参考,具体内容如下问题描述Alice, Bob和Cindy一起玩猜拳的游
- 重写 equals()方法 和 hashCode()方法最近看了学习了集合的简单的知识,碰到了讲解 Set 的部分,感觉很好奇,这里对于 S
- 本文实例为大家分享了Java文件操作的具体代码,供大家参考,具体内容如下简介本程序主要采用了FileInputStream和FileOutp
- 添加jar包这里的Scala不是maven工程所以要找到项目结构(快捷键:同时按住Ctrl+shift+Alt+s)在模块里面添加添加MyS
- 因为公司现在换成了nacos,所以自己写了demo学习一下。结果第一步就走不下去。在使用nacos-config读取nacos配置时。发现b
- java与scala数组及集合的操作这篇博客介绍了scala的数组 + 可变数组的基本使用,及其与java数组的区别scala数组基本操作d
- 1.算法效率算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。时间复杂度主要衡
- Java为什么不浪(long)学而时习之不亦说乎,继续温习Java。今天使用switch时,不小心写了如下代码,报错如下。 public s
- springboot嵌套子类使用在实际项目里,我们会使用到一个User用户含有子类Address、这种嵌套子类在开发中会遇到很多问题,现在主
- 本文实例讲述了Java方法的参数传递机制。分享给大家供大家参考,具体如下:参数传递机制对于程序设计语言来说,一般方法(函数)的参数传递有两种
- 在Java中有两类线程:User Thread(用户线程)、Daemon Thread(守护线程) 用个比较通俗的比如,任何一个守
- 1、修改maven的pom文件只需要将如下依赖添加到pom.xml文件中即可。(注意此处是以plugin的方式,放在<plugins&
- 简单实现了下:import javax.crypto.BadPaddingException;import javax.crypto.Cip
- 正在尝试分配更低的访问权限?在进行Java编程时会给我们报出如下提示怎么办?这里我们将给大家介绍详细的解决方法。首先,查看,控制台给出的提示
- 1.map遍历快速实现边距,文字自适应改变大小Container( // padding: EdgeI
- BeanDefinitionRegistryPostProcessor概述可以看到BeanDefinitionRegistryPostPro