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