求a的b次幂的最后3位（难度：1颗星）

太过爱你忘了你带给我的痛 2022-06-15 07:58 84阅读 0赞

问题描述：

输入a,b，其中a和b的范围是【2,999999999】,求出a的b次幂的最后3位。

PS：  
如果最后三位是001，那么输出1就可以了。

问题分析：

这个问题的实际上是求a的b次幂mod 1000的结果，把这个问题一般化，实际上是a的b次幂mod n的结果。

(X\*Y)%Z=((X%Z)\*(Y%Z))%Z  
根据蒙格马利快速幂模算法，我们可以方便求解，下面举个例子。

2^7：2\*2\*2\*2\*2\*2\*2  
两两分开：(2\*2) \* (2\*2) \* (2\*2) \* 2  
如果用2\*2来计算，那么指数就可以除以2了，不过剩了一个，稍后再单独乘上它。  
再次两两分开，指数除以2： ((2\*2) \* (2\*2)) \* (2\*2) \* 2  
实际上最后一个括号里的2 \* 2是这回又剩下的，那么，稍后再单独乘上它  
现在指数已经为1了，可以计算最终结果了：16 \* 4 \* 2 = 128

把这个积模分解公式公式和上面的求模等式进行结合，就可以得到得到蒙格马利快速幂模算法。

参考代码：

#include <stdio.h>
    
    unsigned Montgomery(unsigned a,unsigned b,unsigned n)
    {
        unsigned ans = 1;
        a %= n;
        while (b > 1)
        {
            if (b & 1)
                ans = (ans * a) % n;
    
            a = (a * a) % n;
            b >>= 1;
        }
    
        return (ans * a) % n;
    
    }
    
    int main()
    {
        printf("%u\n", Montgomery(2, 10000000, 1000));
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220615/1c05ff8d9ac844d0b432bf30d1e1630b.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关求A^B的最后三位数表示的整数。说明：A^B的含义是“A的B次方”（快速幂Java实现）

快速幂思想：（1）对于2的10次方来讲，可以对其进行拆分：2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 快速幂算法的核心思想就是\\每一步

秒速五厘米/ 2023年09月27日 09:01/ 0 赞/ 16 阅读

相关输出菱形图案（难度系数：1颗星）

输入一个整形N表示菱形的边长，输出菱形的图案（每输出一行\就要空一行）如果输入N为3，则输出如下：

港控/mmm°/ 2022年06月17日 11:20/ 0 赞/ 213 阅读

相关计算器（难度系数：3颗星）

题目描述：读入一个只包含 +, -, \, / 的非负整数计算表达式，计算该表达式的值。输入：测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，

喜欢ヅ旅行/ 2022年06月17日 08:16/ 0 赞/ 216 阅读

相关拼音读数字（难度系数：1颗星）

第一题：你的程序要读入一个整数，范围是\[-100000,100000\]。然后，用汉语拼音将这个整数的每一位输出出来。如输入1234，则输出： yi er sa

﹏ヽ暗。殇╰゛Y/ 2022年06月17日 07:29/ 0 赞/ 235 阅读

相关修改百位上的值（难度系数：半颗星）

输入一个大于100的整数，把原数的百位改成6，输出修改后的数（如果原来百位已经是6直接输出）。例如：输入：123456 输出：123656 方法1：把数的

深碍√TFBOYSˉ_/ 2022年06月16日 10:36/ 0 赞/ 153 阅读

相关输出螺旋数组（难度：1颗星）

输入n\n矩阵的n值，打印出一个螺旋矩阵，如下面例子：当n= 5时，输出 1 2 3 4 5 16 17 18

心已赠人/ 2022年06月16日 09:23/ 0 赞/ 261 阅读

相关等差数列（难度：半颗星）

问题描述：一个等差数列的前4个数之和是26，前4个数之积是880，输出这个等差数列的前10项。问题分析：设等差数列的首项为i，公差为j，那么等差数列的和与积分别可以

曾经终败给现在/ 2022年06月15日 09:38/ 0 赞/ 236 阅读

相关分糖果问题（难度：1颗星）

问题描述：有n颗糖果，平均分给班上m个同学（m保证大于1），学生们按照任意顺序领取（反正大家数目都一样），第一个领取的是1颗加上剩余糖果数目的1/10，第二个领取的是2颗加

╰+哭是因爲堅強的太久メ/ 2022年06月15日 09:29/ 0 赞/ 242 阅读

相关求a的b次幂的最后3位（难度：1颗星）

问题描述：输入a,b，其中a和b的范围是【2,999999999】,求出a的b次幂的最后3位。 PS：如果最后三位是001，那么输出1就可以了。问题分析：这

太过爱你忘了你带给我的痛/ 2022年06月15日 07:58/ 0 赞/ 85 阅读