gcd.cpp

来自「数值计算的例子和参考书籍」· C++ 代码 · 共 40 行

#include <stdio.h>

typedef long long LLD;

LLD Gcd(LLD a, LLD b)
{
	return b == 0 ? a : Gcd(b, a % b);
}

void Extended_Gcd(LLD a, LLD b, LLD *x, LLD *y)
{
	LLD X, Y;
	if(b == 0)
	{
		*x = 1;
		*y = 0;
	}
	else
	{
		Extended_Gcd(b, a % b, &X, &Y);
		*x = Y;
		*y = X - a / b * Y;
	}
}

int main(void)
{
	LLD x, y, k, a, n;
	while(scanf("%lld %lld",&a, &n), a != 0 || n != 0)
	{
		Extended_Gcd(a, n, &x, &y);
		if(x < 0)
		{
			x += n;
		}
		printf("%lld\n",x);
	}
	return 0;
}