gcd_extended.cpp

实现《现代密码学理论与实践》中

#include"stdio.h"

int gcd_extended(int a,int b,int *u,int *v)
{
    int i=1,r[1024]={1},q;
	r[0]=a;
	r[1]=b;
	u[0]=1;
	u[1]=0;
	v[0]=0;
	v[1]=1;
	for(;r[i]!=0;)
	{
	    q=r[i-1]/r[i];
		u[i+1]=u[i-1]-q*u[i];
		v[i+1]=v[i-1]-q*v[i];
		i++;
		r[i]=a*u[i]+b*v[i];
	}
	for(int j=0;j<i;j++)
	{
		printf("i=%d: u[%d]=%d,v[%d]=%d\n",j,j,u[j],j,v[j]);
	}
    return r[i-1];

}

void main()
{
    int a,b,c,u[1024]={1},v[1024]={1};
	scanf("%d%d",&a,&b);
    c=gcd_extended(a,b,u,v);	
	printf("gcd=%d\n",c);

}