Euclid Problem/문보창

소감 ¶

2005/03/31 Accepted 0:01.820 436
예전에 정수론 책에서 본 유클리드 알고리즘의 응용문제이다. AX + BY = GCD 에서 gcd와 x, y 구하는 법을 문보창페이지에 원래 가지고 있었기 때문에 단순한 copy&paste로 문제를 풀 수 있었다.

코드 ¶

~cpp 
// no10104 - Euclid Problem
#include <iostream>
#include <cmath>
using namespace std;

int gcd(int p, int q, int & x, int & y);

int main()
{
	int a, b;
	int x, y;
	int g;				// gcd
	while (cin >> a >> b)
	{	
		g = gcd(a, b, x, y);
		cout << x << " " << y << " " << g << endl;
	}
	return 0;
}

int gcd(int p, int q, int & x, int & y) 
{ 
        int x1, y1;             // 이전계수 
        int g;                  // gcd 
 
        if (p < q) 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; 
}

나한테 할 말 ¶

EuclidProblem AOI 문보창