imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:14Z

New page

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

==== 코드 ====
// 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]] [[문보창]]

EuclidProblem/문보창 - Revision history

imported>Unknown at 05:23, 7 February 2021