== 소감 ==
2005/04/10 Accepted 0:01.855 440
통과했다고 말하긴 뭐함(결국 책에 있는 코드 이용) 나중에 다시 도전할 생각
수학적지식이 부족함을 절실히 느낌
== 소스 ==
{{{~cpp 
#include <iostream>
using namespace std;
#include <climits>
#include <cmath>

long gcd(long p, long q, long *x, long *y)
{
	long x1, y1;
	long g;
	if (q > p)
		return gcd(q, p, y, x);
	if (q == 0)
	{
		*x = 1;
		*y = 0;
		return p;
	}
	g = gcd(q, p % q, &x1, &y1);
	*x = y1;
	*y = (x1 - floor(p / q) * y1);
	return g;
}

int main()
{
	int a, b;
	while (cin >> a >> b)
	{
		/*int u = a, v = b;
		while (v != 0)
		{
			int temp = u % v;
			u = v;
			v = temp;
		}
		int gcd = u;

		int i, j;
		int x = 0, y = 0;

		int a2 = a / gcd;
		int b2 = b / gcd;

		int minsum = INT_MAX - 1;
		
		// 나머지를 이용해서 어떻게 해보려다 실패
		/*while (!(a2 == 1 && b2 == 1))
		{
			int temp1, temp2;
			temp1 = (a2 - 1) / b2;
			y += temp1;
			//x *= temp1;
			a2 = a2 - temp1 * b2;
			temp2 = (b2 - 1) / a2;
			x += temp2;
			y *= temp2;
			b2 = b2 - temp2 * a2;
		}
		//y += 1;

		int min, max;
		if (a2 < b2)
		{
			min = a2;
			max = b2;
		}
		else
		{
			min = b2;
			max = a2;
		}

		// 1차이 나는 배수를 구한다 but 시간오버
		for (i = 1; ; i++)
		{
			if ((max * i - 1) % min == 0)
			{
				x = -1 * ((max * i - 1) / min);
				y = i;
				break;
			}
			else if ((max * i + 1) % min == 0)
			{
				x = (max * i + 1) / min;
				y = -1 * i;
				break;
			}
		}

		if (a2 == min)	
			cout << x << " " << y << " " << gcd << endl;
		else*/

		// 결국 책에 있는 방법
		long x, y;
		int g = gcd(a, b, &x, &y);

		cout << x << " " << y << " " << g << endl;
	}

	return 0;
}

}}}
== 댓글 ==

----
[EuclidProblem]