无声的月

 

a^b mod n 求最大公约数,及其扩展

a^b mod n
 1long long  ModExp(long long  a, long long b, long long n)  
 2{
 3   long long result=1, y=a;
 4   while (b)
 5  {
 6     if (b%2 == 1)
 7       result = result * y % n;
 8     y = y * y % n;
 9     b/=2;
10   }

11   return result;
12}

13


求最大公约数,及其扩展
 1 int Euclid(int a,int b)//a>=b,求a,b的最大公约数
 2 {
 3     if(b==0)
 4     return a;
 5     else
 6     return Euclid(b,a%b);
 7 }
 8 int EuclidExtension(int a,int b,int &x,int &y)//a>=b ,求d=ax+by的x,y,其中d为两者的最大公约数
 9 {
10    
11     if(b==0)
12     {
13         x=1;
14         y=0;
15         return 1;
16     }
17     else
18     {
19         int x1,y1;
20         int d1=EuclidExtension(b,a%b,x1,y1);
21         x=y1;
22         y=x1-((int)(a/b))*y1;
23         return d1;
24     }
25 }

posted on 2010-06-23 11:43 Baron 阅读(278) 评论(0)  编辑 收藏 引用


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


导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜