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