高次幂求模

淡淡的烟草味﹌ 2022-02-09 09:27 529阅读 0赞

主要的思想是来自一个公式：a\*b%c = (a%c) \*(b%c) %c

**基本概念及思想**

对形如a^b mod m 的运算（b一般较大）

但a,b,m都在long型范围内

算法的主要思想是分治，分而治之。将大的问题分成若干个相似的较小的问题！

具体实现是用递归的方法！

举例

2^100mod 3

像这种运算如果先算出2^100 的值，然后再模上3，相信比较困难！

我们可以将100变小点

2^100=(2^50)^2 =((2^25)^2)^2=((((2^1)^2)^2)…)^2

若我们已经得出250 mod 3的值，我们便很简单地得出2^100mod 3的值。

按照上述的方法继续分下去…

最终肯定会得到2^1mod 3 这种情况！这样就好办了！这便是递归的边界，到此我们就可以返回2 mod 3的值了！

另一个问题，再分时有两种情况！

2^100=(2^50)2        , 100是偶数

2^99=(2^49)2 \*2   , 99是奇数

第二种情况需要在第一种情况上乘上一次基数。

递归算法代码如下

![复制代码][copycode.gif]

1 long mod(long a,long b,long c)
     2 {
     3     long ans;
     4     if(!b)return 1;
     5     else if(b==1)return a%c;
     6     else ans = mod(a,b/2,c);
     7     ans = (ans*ans)%c;
     8     if(b&1)ans = (ans*(a%c))%c;
     9     return ans;
    10 }

![复制代码][copycode.gif]

另一种高效的算法是用循环代替递归算法

![复制代码][copycode.gif]

1 long mod_loop(long a,long b,long c)
     2 {
     3     long ret=1,tem=a;
     4     while(b)
     5     {
     6         if(b&1) ret = ret*tem%c;
     7         tem = tem*tem%c;
     8         b>>=1;
     9     }
    10     return ret;
    11 }

![复制代码][copycode.gif]

本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/archive/2012/04/24/2468656.html ，如需转载请自行联系原作者

[copycode.gif]: /images/20220206/d3214e0c5e5d40769b5051a9704a6e46.png

发表评论取消回复

表情：

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

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

相关阅读

相关 c++求a的b次方/次幂

![watermark,type\_d3F5LXplbmhlaQ,shadow\_50,text\_Q1NETiBA6LaFMzM4,size\_20,color\_FFFFF

r囧r小猫/ 2023年09月30日 10:43/ 0 赞/ 5 阅读

相关 python实现pow函数（求n次幂，求n次方）

实现 pow(x, n)，即计算 x 的 n 次幂函数。其中n为整数。解法1：暴力法不是常规意义上的暴力，过程中通过动态调整底数的大小来加快求解。代码如下：

冷不防/ 2022年10月08日 02:28/ 0 赞/ 190 阅读

相关 NYOJ 102 次方求模

次方求模时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述求a的b次方对c取余的值输入第一行输入一个整数n表示测试数据的组数

谁借莪１个温暖的怀抱￠/ 2022年08月25日 01:50/ 0 赞/ 178 阅读

相关【算法】求n的m次方（快速幂取模）

题目求n的m次方，n，m均为自然数。解析看似简单的题目，但是要想写的高效还不是那么容易想出来。实现 unsigned int power(

以你之姓@/ 2022年08月09日 06:45/ 0 赞/ 240 阅读

相关求高精度幂

<table style="font-family:Simsun"> <tbody> <tr> <td> <div style="text-alig

分手后的思念是犯贱/ 2022年08月01日 11:15/ 0 赞/ 156 阅读

相关求方幂模s = a^j mod p

在编写程序时，经常求方幂模，即s = a^j mod p 而如果先求a^j，则可能会导致溢出，于是采用了一种避免溢出的算法ModularExponent 伪代码：

青旅半醒/ 2022年07月14日 08:11/ 0 赞/ 156 阅读

相关整数快速幂——次方求模

先上代码： unsigned Power(unsigned n, unsigned p) \{ // 计算n的p次方 unsigned odd = 1; //

迷南。/ 2022年06月12日 01:36/ 0 赞/ 231 阅读

相关求高精度幂

周末闲着没事看了下acm的题目，要求计算高精度幂，即一个数的n次幂。代码中的大数用STL中的string表示本文所实现的方法效率不一定达到acm的要求(没有进行性能测试)

朴灿烈づ我的快乐病毒、/ 2022年05月14日 10:59/ 0 赞/ 187 阅读

相关【算法】同余定理及快速幂求模

文章目录定义及其性质大数的高精度对单精度取模快速幂取模(次方求模) 定义及其

港控/mmm°/ 2022年04月01日 10:00/ 0 赞/ 372 阅读

相关高次幂求模

主要的思想是来自一个公式：a\b%c = (a%c) \(b%c) %c 基本概念及思想对形如a^b mod m 的运算（b一般较大）但a,b,m都在lo

淡淡的烟草味﹌/ 2022年02月09日 09:27/ 0 赞/ 530 阅读