快速幂运算

朴灿烈づ我的快乐病毒、 2022-07-26 06:31 208阅读 0赞

/\*  
\* 基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注  
给出3个正整数A B C，求A^B Mod C。  
例如，3 5 8，3^5 Mod 8 = 3。  
Input  
3个正整数A B C，中间用空格分隔。(1 <= A,B,C <= 10^9)  
Output  
输出计算结果  
Input示例  
3 5 8  
Output示例  
3  
\* \*/

import java.util.Scanner;
    
    public class Main {
    
        public static long powMod(long a,long b,long c){
            long res = 1;
            while(b>0){
                if((b&1)==1){
                    res = ((res%c)*(a%c))%c;
                }
                b >>= 1;
                a = ((a%c)*(a%c))%c;
            }
            return res;
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            long a = in.nextLong();
            long b = in.nextLong();
            long c = in.nextLong();
            long res = powMod(a,b,c);
            System.out.println(res);
        }
    
    }

求a^n，先不考虑是否会超出数据表示的精度范围，如果是用for(1:n)循环的话，时间复杂度为O(n)，若n值为10^9，往往在oj中就会超时。然而，n是可以用二进制表示的，n = 2^k1 + 2^k2 + 2^k3 + …+ 2^kn （共有log n项）， 令pi = 2 ^ ki，则n=p1+p2+…+pn，哪么a ^ n = a^p1 \* a^p2 \* a^p3\*….\*a^pn，哪么原先n项相乘就变为了log n项相乘，时间复杂度从O(n)转变为O(log n) 。

> 现在要求A^156,而156(10)=10011100(2)  
> 也就有A^156=>(A^4)*(A^8)*(A^16)\*(A^128) 考虑到因子间的联系，我们从二进制10011100中的最右端开始计算到最左端。细节就说到这，下面给核心代码：  
> res = 1;  
> while(N)  
> \{  
> if(N&1)  
> res=res\*A;  
> N>>=1;  
> A=A\*A;//A是在变化的，每一位都是前一位乘以”A“  
> \}

发表评论取消回复

表情：

评论列表（有 0 条评论，208人围观）

还没有评论，来说两句吧...

相关阅读

相关幂运算

幂的概念：幂是乘方运算得结果，乘方运算涉及三个概念底数、指数和幂，如下图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

谁借莪１个温暖的怀抱￠/ 2022年12月11日 02:22/ 0 赞/ 141 阅读

相关快速幂运算

include<iostream> using namespace std; typedef long long ll;

今天药忘吃喽~/ 2022年08月03日 14:52/ 0 赞/ 151 阅读

相关快速幂运算

/\ \ 基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注给出3个正整数A B C，求A^B Mod C。例如，3 5

朴灿烈づ我的快乐病毒、/ 2022年07月26日 06:31/ 0 赞/ 209 阅读

相关矩阵运算，矩阵快速幂，模板

include<cstdio> include<algorithm> include<cstring> include<iostream>

以你之姓@/ 2022年06月11日 05:41/ 0 赞/ 220 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 297 阅读

相关快速幂和矩阵快速幂

前言新年第一篇技术类的文章，应该算是算法方面的文章的。看标题：快速幂和矩阵快速幂，好像挺高大上。其实并不是很难，快速幂就是快速求一个数的幂（一个数的 n 次方）。

╰+攻爆jí腚メ/ 2022年06月01日 08:10/ 0 赞/ 288 阅读

相关矩阵快速幂+整数快速幂

嗯~ 今天总结一下快速幂的知识点 1.首先讲一下矩阵相乘矩阵A与矩阵B相乘的前提条件：A矩阵的列必须和矩阵B的行相等。若A矩阵是m\p的矩阵，那么B矩阵必定是p\n的

缺乏、安全感/ 2022年05月11日 13:22/ 0 赞/ 324 阅读

相关快速幂

快速幂快速幂，实际上是快速幂取模的缩写。简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法

刺骨的言语ヽ痛彻心扉/ 2022年04月17日 05:29/ 0 赞/ 233 阅读

相关组合数学 (一): 快速幂运算

快速幂快速幂运算 C语言实现应用快速幂运算普通幂运算复杂度为 O(N) 快速幂运算复杂度为 O(lgN) 举个例子: 如

谁践踏了优雅/ 2022年03月21日 08:58/ 0 赞/ 273 阅读

相关幂运算

//1.基本实现方法递归时间复杂度O(n) double pow(int x,int n){ if(n<0)

短命女/ 2021年09月26日 13:06/ 0 赞/ 295 阅读