拓展的欧几里得.cpp

来自「acm中各种代码」· C++ 代码 · 共 25 行

#include<stdio.h>
int ext_gcd(int a,int b,int& x,int& y){
	int t,ret;
	if (!b)
    {
		x=1,y=0;
		return a;
	}
	ret=ext_gcd(b,a%b,x,y);
	t=x,x=y,y=t-a/b*y;
	printf("%d %d\n",x,y); 
	return ret;
}
int main()
{
    int a,b,c;
    int x,y;
    while(scanf("%d %d",&a,&b) != EOF)
    {
     c = ext_gcd(a,b,x,y);
    printf("%d\n",c);
    c--;
   }
}