Java语言实现快速幂取模算法详解

快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的,在朴素的方法中我们计算一个数比如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循环,的到最后的结果。

总结

以上就是本文关于Java语言实现快速幂取模算法详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

时间: 2017-11-28

Java基于分治算法实现的棋盘覆盖问题示例

本文实例讲述了Java基于分治算法实现的棋盘覆盖问题.分享给大家供大家参考,具体如下: 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖.四个L型骨牌如下图: 棋盘中的特殊方格如图: 实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不

Java实现DFA算法对敏感词、广告词过滤功能示例

一.前言 开发中经常要处理用户一些文字的提交,所以涉及到了敏感词过滤的功能,参考资料中DFA有穷状态机算法的实现,创建有向图.完成了对敏感词.广告词的过滤,而且效率较好,所以分享一下. 具体实现: 1.匹配大小写过滤  2.匹配全角半角过滤  3.匹配过滤停顿词过滤.  4.敏感词重复词过滤. 例如: 支持如下类型类型过滤检测: fuck 全小写 FuCk 大小写 fuck全角半角 f!!!u&c ###k 停顿词 fffuuuucccckkk 重复词 敏感词过滤的做法有很多,我简单描述我现在理

Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例

本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积.分享给大家供大家参考,具体如下: 什么是笛卡尔积? 在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员. 假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}. 如何用程序算法实现笛卡尔积? 如果编程前已知集合的数量

关于JAVA经典算法40题(超实用版)

[程序1]题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第四个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?1.程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21....public class exp2{ public static void main(String args[]){ int i=0; for(i=1;i<=20;i++)System.out.println(f(i));}public static int f(in

基于Java实现的图的广度优先遍历算法

本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

Java语言实现Blowfish加密算法完整代码分享

前几天网上突然出现流言:某东发生数据泄露12G,最终某东在一篇声明中没有否认,还算是勉强承认了吧,这件事对于一般人有什么影响.应该怎么做已经有一堆人说了,所以就不凑热闹了,咱来点对程序猿来说实际点的,说一个个人认为目前比较安全的加密算法:Blowfish. 上代码之前,先说几点Blowfish加密算法的特点: 1. 对称加密,即加密的密钥和解密的密钥是相同的: 2. 每次加密之后的结果是不同的(这也是老夫比较欣赏的一点): 3. 可逆的,和老夫之前的文章介绍的md5等摘要算法不一样,他是可逆的:

基于Java实现的一层简单人工神经网络算法示例

本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect

Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

本文实例讲述了Java基于栈方式解决汉诺塔问题.分享给大家供大家参考,具体如下: /** * 栈方式非递归汉诺塔 * @author zy * */ public class StackHanoi { /** * @param args */ public static void main(String[] args) { System.out.println("我们测试结果:"); System.out.println("递归方式:"); hanoiNormal(

Java编程实现A*算法完整代码

前言 A*搜寻算法俗称A星算法.这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法.常用于游戏中 通过二维数组构建的一个迷宫,"%"表示墙壁,A为起点,B为终点,"#"代表障碍物,"*"代表算法计算后的路径 本文实例代码结构: % % % % % % % % o o o o o % % o o # o o % % A o # o B % % o o # o o % % o o o o o % % % % % % % % =======

Java矩阵连乘问题(动态规划)算法实例分析

本文实例讲述了Java矩阵连乘问题(动态规划)算法.分享给大家供大家参考,具体如下: 问题描述:给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1.确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少.输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数. 问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序.这种计算次序可以用加括号的方式来确定.若一个矩阵连乘积的计算次序完全确

70行Java代码实现深度神经网络算法分享

对于现在流行的深度学习,保持学习精神是必要的--程序员尤其是架构师永远都要对核心技术和关键算法保持关注和敏感,必要时要动手写一写掌握下来,先不用关心什么时候用到--用不用是政治问题,会不会写是技术问题,就像军人不关心打不打的问题,而要关心如何打赢的问题. 程序员如何学习机器学习 对程序员来说,机器学习是有一定门槛的(这个门槛也是其核心竞争力),相信很多人在学习机器学习时都会为满是数学公式的英文论文而头疼,甚至可能知难而退.但实际上机器学习算法落地程序并不难写,下面是70行代码实现的反向多层(BP

如何用120行Java代码写一个自己的区块链

区块链是目前最热门的话题,广大读者都听说过比特币,或许还有智能合约,相信大家都非常想了解这一切是如何工作的.这篇文章就是帮助你使用 Java 语言来实现一个简单的区块链,用不到 120 行代码来揭示区块链的原理! "用不到120行 Java 代码就能实现一个自己的区块链!" 听起来不可思议吧?有什么能比开发一个自己的区块链更好的学习实践方法呢?那我们就一起来实践下! 因为我们是一家从事互联网金融的科技公司,所以我们采用虚拟资产金额作为这篇文章中的示例数据.大家可以先为自己想一个数字,后

Java代码实践12306售票算法(二)

周五闲来无事,基于上一篇关于浅析12306售票算法(java版)理论,进行了java编码实践供各位读者参考(以下为相关代码的简单描述) 1.订票工具类 1.1初始化一列车厢的票据信息 /** * 生成Ticket信息 * * @param train * @return */ public static List<Ticket> initTicketList(Train train) { List<Ticket> result = new ArrayList<Ticket&g

200行Java代码编写一个计算器程序

发现了大学时候写的计算器小程序,还有个图形界面,能够图形化展示表达式语法树,哈哈;) 只有200行Java代码,不但能够计算加减乘除,还能够匹配小括号~ 代码点评: 从朴素的界面配色到简单易懂错误提示,无不体现了"用户体验"至上的设计理念:代码异常处理全面合理.滴水不漏,代码缩进优雅大方,变量命名直观易懂:再结合长度适中简单明了的注释,程序整体给人一种清新脱俗之感.背后不难看出作者对学习的热爱以及对设计的苛求,工匠精神可见一斑,真可谓是大学数据结构学以致用的典范! 实现代码如下所示:

使用70行Python代码实现一个递归下降解析器的教程

 第一步:标记化 处理表达式的第一步就是将其转化为包含一个个独立符号的列表.这一步很简单,且不是本文的重点,因此在此处我省略了很多. 首先,我定义了一些标记(数字不在此中,它们是默认的标记)和一个标记类型: token_map = {'+':'ADD', '-':'ADD', '*':'MUL', '/':'MUL', '(':'LPAR', ')':'RPAR'} Token = namedtuple('Token', ['name', 'value']) 下面就是我用来标记 `expr` 表

200行Java代码如何实现依赖注入框架详解

依赖注入介绍 先回顾下依赖注入的概念: 我们常提起的依赖注入(Dependency Injection)和控制反转(Inversion of Control)是同一个概念.具体含义是:当某个角色(可能是一个Java实例,调用者)需要另一个角色(另一个Java实例,被调用者)的协助时,在 传统的程序设计过程中,通常由调用者来创建被调用者的实例.但在Spring里,创建被调用者的工作不再由调用者来完成,因此称为控制反转;创建被调用者 实例的工作通常由Spring容器来完成,然后注入调用者,因此也称为

仅利用30行Python代码来展示X算法

假如你对数独解法感兴趣,你可能听说过精确覆盖问题.给定全集 X 和 X 的子集的集合 Y ,存在一个 Y 的子集 Y*,使得 Y* 构成 X 的一种分割. 这儿有个Python写的例子. X = {1, 2, 3, 4, 5, 6, 7} Y = { 'A': [1, 4, 7], 'B': [1, 4], 'C': [4, 5, 7], 'D': [3, 5, 6], 'E': [2, 3, 6, 7], 'F': [2, 7]} 这个例子的唯一解是['B', 'D', 'F']. 精确覆盖问

200行java代码实现2048小游戏

本文实例为大家分享了java实现2048小游戏的具体代码,供大家参考,具体内容如下 效果图: 游戏介绍: 1.2048是一款益智类小游戏,刚开始随机出现两个数字,可以上下左右控制数字的移动. 2.当选择一个方向移动后,所有数字都会沿该方向移动到表格尽头,并且空余表格会随机出现2或4,当碰到相同的两个数字时,该两个数字会合并相加成一个数字,直到最大的数字变成2048游戏成功 3.否则当数字填满表格且不能再移动时游戏失败. 游戏代码: import java.awt.*; import java.a

Java版超大整数阶乘算法代码详解-10,0000级

当计算超过20以上的阶乘时,阶乘的结果值往往会很大.一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围.如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决.在网上我看到很多用C.C++和C#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章.数组越界,一眼就可以看出程序本身无法运行.转载他人文章的时候,代码倒是仔细看看啊.唉,粗糙.过年了,在家闲来蛋疼,仔细分析分析,用Java实现了一个程序计算超大整数阶乘.思想取自网上,由我个人优化和改进. 这个方法采用"数

Python 25行代码实现的RSA算法详解

本文实例讲述了Python 25行代码实现的RSA算法.分享给大家供大家参考,具体如下: 网络上很多关于RSA算法的原理介绍,但是翻来翻去就是没有一个靠谱的算法实现,即使有代码介绍,也都是直接调用JDK或者Python代码包中的API实现,或者即使有代码也都写得特别烂.无形中让人感觉RSA加密算法竟然这么高深,然后就看不下去了.还有我发现对于"大整数的幂次乘方取模"竟然采用直接计算的幂次的值,再取模,类似于(2 ^ 1024) ^ (2 ^ 1024),这样的计算就直接去计算了,我不知