Localhost8080

知行合一，自强不息

 

快速幂取模算法

1,乘法模运算规则:
(a * b) % n = (a % n * b % n) % n  
2,模取幂运算a^b mod c:  a*b%n=a*(b%n)%n
b如果比较大,可以利用所谓的二分法,b=b0+b1*2^1+b2*2^2+...+bn*2^n从最低位b0开始，由右至左逐位扫描.
3,实例代码:

#include <iostream>      
using namespace std;      
  
//计算a^bmodn      
int modexp(int a,int b,int n)      
{      
    int ret=1;      
    int tmp=a;      
    while(b)      
    {      
       //基数存在      
       if(b&0x1) ret=ret*tmp%n;      
       tmp=tmp*tmp%n;      
       b>>=1;      
    }      
    return ret;      
}      

int main()      
{      
    cout<<modexp(2,10,3)<<endl;      
    return 0;      
}

posted on 2010-05-25 21:40 superKiki 阅读(1325) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔档案

文章分类

我的好友

一些常去的网站

搜索

最新评论

阅读排行榜

评论排行榜