当前位置:编程学习 > C/C++ >>

欧几里德算法(C语言)

侠客行
#include <stdio.h>
void luwei_易做图(int a,int b,int &d,int &x,int &y )
{
        if(b==0) //对于ax+by=d且b=0,显然有x=1(因为易做图(a,b) = d,可知a=d)
        {
                d=a;
                x=1;
                y=0;
                return ;
        }
        luwei_易做图(b,a%b,d,y,x);//a*x+b*y=d可转化为b*y+(a%b)*(y-x*(a/b))=d
        y -= x * (a/b) ;//在回溯时x = y,y = y-x*(a/b),更新x,y的值
}
// ax ≡ 1 (mod n) 满足易做图(a,n) = 1,该问题可化为ax + bn = 1,然后上面的函数,即可求出x
int shuchu (int a ,int n)
{
        int d,x,y ;
        luwei_易做图(a,n,d,x,y);
        if(d==1) //ax + bn = 1
        {
                x=x%n;
                if(x<0)
               return (x+n)%n;//返回的值保证是正数
               printf("a mod b 的逆元为:%dn",x);
               printf("b mod a 的逆元为:%dn",(1-a*(x-26))/n);
        }
        else
                printf("a 与 b 不互素,不存在逆元n");
}

int main()
{
    int a,b;
    printf("输入两个正整数:(a<b)n");
    scanf("%d%d",&a,&b);
    shuchu(a,b);
    return 0;
}

\

补充:软件开发 , C语言 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,