欧几里德算法（C语言）

		
侠客行
#include <stdio.h>
void luwei_gcd(int a,int b,int &d,int &x,int &y )
{
        if(b==0) //对于ax+by=d且b=0,显然有x=1(因为gcd(a,b) = d,可知a=d)
        {
                d=a;
                x=1;
                y=0;
                return ;
        }
        luwei_gcd(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) 满足gcd(a,n) = 1,该问题可化为ax + bn = 1,然后上面的函数，即可求出x
int shuchu (int a ,int n)
{
        int d,x,y ;
        luwei_gcd(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语言 ,

上一个：RC4算法 N=3（C语言）
下一个：漫谈算法（五）问题复杂度分析（Problem Complexity and Adversarial Lower&nbsp