快速幂算法

饶文津

发布于 2020-05-31 23:40:48

4450

发布于 2020-05-31 23:40:48

文章被收录于专栏：饶文津的专栏饶文津的专栏

快速幂算法思想：迭代/二进制

我们知道一个公式：a*b%c=（a%c*b%c）%c

如果要求ab%c：

一、迭代

　　当b为奇数：ab%c=（（a2）b/2*a）%c，记k=a2%c，那就是求（kb/2%c*a)%c

　　当b为偶数：ab%c=（a2）b/2%c,记k=a2%c，那就是求kb/2%c

　　然后问题转化为求kb/2%c，

　　我们假设

令k1=a2%c，问题转化为求k1b/2%c

令k2=k12%c=a4%c，问题转化为求k2b/4%c

令k3=k22%c=a8%c，问题转化为求k3b/8%c

……

这个过程就可以迭代下去，一开始k=a，每次b=b/2，k=k*k%c，每当b为奇数时，都要把此时的k（还未平方的）乘进答案，求到最后，b=1时（最后b一定先=1，然后=0），答案就一定会乘进去的，然后b=0就结束算法了。

#include<stdio.h>
int main(){
    int a,b,c,k,ans;
    scanf("%d%d%d",&a,&b,&c);
    ans=1;
    k=a;
    while(b){
        if(b%2)//b是奇数
            ans=ans*k%c;
        k=k*k%c;
        b=b/2;
    }
    printf("%d",ans);
    return 0;
}

二、二进制

　　假设b=（18）10=（10010）2

　　那ab%c=a（10）2*a（10000）2%c=a2*a16%c

　　每次循环就相当于对b的二进制位从右到左审查，如果为1，那就乘上k，

　　k是什么? 就是a以b的这个二进制位为幂的值，比如到了10010的从右到左第二个位置时，k=a（10）2=a2，到了第五个位置时，k=a（10000）2=a16

　　所以每次k=k*k%c，k的变化是：k=a（1）2%c，k=a（10）2%c，k=a（100）2 %c，……

#include<stdio.h>
int main(){
    int a,b,c,k,ans;
    scanf("%d%d%d",&a,&b,&c);
    ans=1;
    k=a;
    while(b){
        if(b&1)//b的二进制的最后一位为1
            ans=ans*k%c;
        k=k*k%c;
        b=b>>1;//b的二进制去掉最后一位
    }
    printf("%d",ans);
    return 0;
}

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2015-12-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客?前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度