● 扩展的欧几里得算法求乘法逆元 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: ACMICPC
标  题: 扩展的欧几里得算法求乘法逆元
发信站: 荔园晨风BBS站 (Sun Jul 25 14:59:21 2004), 站内信件

相关的知识请自行参看数论相关知识。。。

//用扩展的欧几里得算法求乘法逆元
//如果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 S-Term软件网络书店