EuclidProblem/차영권

소감

2005/04/03 Accepted 0:01.818 440 유클리드 호제법과 디오판토스 방정식에 대해 공부해 볼 수 있는 좋은 기회였다고 생각한다.

코드

// Euclidean.cpp
#include <iostream.h>

#define MAX 50

struct Coefficient {
	int X;
	int Y;
}coefficient[MAX];

int gcd(int max, int min);

int main()
{
	int a, b;
	while (cin >> a >> b)
	{
		int i = 1, j;
		int GCD, reminder; 
		GCD = gcd(a >= b ? a : b, a <= b ? a : b);
		coefficient[0].X = 0;		coefficient[0].Y = 1;
		reminder = a%b;
		while (reminder != 0)
		{
			coefficient[i].X = 1;
			coefficient[i++].Y = -a/b;
			reminder = a%b;
			a = b; b = reminder;	
		}
		// X, Y값을 계산한다
		for (j=1 ; j<i-1 ; j++)
		{	
			coefficient[j+1].X = coefficient[j+1].Y * coefficient[j].X + coefficient[j-1].X;
			coefficient[j+1].Y = coefficient[j+1].Y * coefficient[j].Y + coefficient[j-1].Y;
		}
		cout << coefficient[j-1].X << " " << coefficient[j-1].Y << " " << GCD << endl;
	}
	return 0;
}

int gcd(int max, int min)
{
	if (max%min == 0)
		return min; 
	else
		return gcd(min, max%min);
}

---