소감 ¶
문제가 있길래 한번 도전해봤습니다. 참여하는데 다른 룰이 있는 것 인지 모르겠군요.
유클리드호제법을 까먹어서 고등학교 정석책을 참고
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);
}
