감 ¶
문가 길래 봤다. 는데 다른 룰 는 것 모르겠군.
리드법 까먹 고교 고
X, Y를 구는 드 대공를 구는 드를 는데 렸다.
리드법 까먹 고교 고
X, Y를 구는 드 대공를 구는 드를 는데 렸다.
드 ¶
~cpp
//Euclid Problem/동 2005.04.03
#include <iostream>
using namespace std;
long Eucl(long, long);
long xy[2][2] = {{0,0},{0,1}};
int main(void){
long a, b, gcd;
cin >> a >> b;
bool isSwap = false;
if(a<b){ //a는 무 를 는다.
isSwap = true;
swap(a, b);
}
gcd = Eucl(a,b);
if(isSwap==true)
swap(xy[1][0],xy[1][1]);
cout << xy[1][0] << " " << xy[1][1] << " " << gcd <<"\n";
return 0;
}
long Eucl(long a, long b){ //a가 . a=bq+r공 변 r=a-qb a,b
if(a%b == 0)
return b;
long q = (a - a%b)/b;
long tx = xy[0][0], ty = xy[0][1];
xy[0][0] = xy[1][0];
xy[0][1] = xy[1][1];
if(tx==0 && ty==0){//라면
xy[1][0] = 1, xy[1][1] = q*-1; // a 는 나 1다.
}
else{
xy[1][0] = xy[0][0]*-1*q+tx; // 몫q*-1 고 를 더다.
xy[1][1] = xy[0][1]*-1*q+ty;
}
return Eucl(b, a%b);
}
