Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:02Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 110:		Line 110:
	----		----
	[[EuclidProblem]]		[[EuclidProblem]]

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:14Z

New page

== 소감 ==
2005/04/10 Accepted 0:01.855 440
통과했다고 말하긴 뭐함(결국 책에 있는 코드 이용) 나중에 다시 도전할 생각
수학적지식이 부족함을 절실히 느낌
== 소스 ==
#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]]

EuclidProblem/곽세환 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021