荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: huhaiming (一生只爱她), 信区: Program
标 题: 扩展的欧几里得算法求乘法逆元
发信站: 荔园晨风BBS站 (Sun Jul 25 15:01:25 2004), 转信
【 以下文字转载自 ACMICPC 讨论区 】
【 原文由 huhaiming 所发表 】
相关的知识请自行参看数论相关知识。。。
//用扩展的欧几里得算法求乘法逆元
//如果gcd(d,f)=1,那么d有一个模f的乘法逆元。即对于小于f的正整数d,
//存在一个小于f的整数d^-1,使得d*d^-1 = 1 mod f
//by jhun 2003.5.4
#include <stdio.h>
//欧几里得算法求gcd(p,q) 辗转相除法
int Enclid(int p,int q)
{
if(q==0) return p;
else return Enclid(q,p%q);
}
//扩展的欧几里得算法求乘法逆元
int ExtEnclid(int d,int f)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
if(d>f) d=d+f-(d=f); //交换d和f使得d<f
x1=1,x2=0,x3=f;
y1=0,y2=1,y3=d;
while(1)
{
if(y3==0) return 0; //没有逆元,gcd(d,f)=x3
if(y3==1) return y2; //逆元为y2,gcd(d,f)=1
k=x3/y3;
t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;
x1=y1,x2=y2,x3=y3;
y1=t1,y2=t2,y3=t3;
}
}
int main()
{
int d,f,res;
printf("you can try d=550 f=1769, d^-1 = 550, press ctrl+Z to
quit...\n");
printf("intput the d and f value:\n");
while(scanf("%d%d",&d,&f)==2)
{
printf("Enclid : gcd(%d,%d)=%d\n",d,f,Enclid(d,f));
res=ExtEnclid(d,f);
if(res==0) printf("Not Exist the d^-1\n");
else
if(res>0) printf("ExtenderEnclid : d^-1 = %d ,
%d * %d = 1 mod %d\n",res,d,res,f);
else
{
printf("ExtenderEnclid : d^-1 = (%d) ,
%d * (%d) = 1 mod %d\n",res,d,res,f);
printf("ExtenderEnclid : d^-1 = %d , %d *
%d = 1 mod %d\n",res+f,d,res+f,f);
}
}
return 0;
}
--
菩提本无树,明镜亦非台
本来无一物,何处惹尘埃
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.21.224.234]
--
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.21.224.234]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店