/*카잉 달력에 대해서 풀어보도록 하겠습니다. 에과 에보다 작거나 같은 두 개의 자연수 엑스 와이를 가지고 각 년도를 엑스 와이와 같은 형식으로 표현 처번쨰 해를 1대1 두번째 해를 2대2 엑스가 엠이면 엑스 바는 엑스플러스 1이고 ㅡ렇지 않으면 엑스뉴는 1이다 같은 방식 와이도 마찬가지 입니다. 엠엔은 그들 달력의 마지막 해로 종말이 도래 한다 엠이 10 엔이 12 이면 첫번째 해 11번째해는 1:11 로 표현 됩니다. 1:1 2:2 3:3 4:4 5:5 66 77 88 99 10 10 간다음에 1 11 2 12 3 1 이 됩니다. 오케이요 각각 따로 따로 움직인다고 보면 되겠습니다. 오케이 명확한 규칙이 존재합니다. 일단 테스트 케이스는 받지 않겠습니다. 10 12 3 9 는 33 을 나타냅니다. 오케이요. 그럼 예를 들어서 1:1 -> 2:2 -> 3:3 -> 이런식으로 올라갑니다. 오케이 리셋하고 리셋하고 이런것 특이하게 하네요 숫자 세는 것을 3 9 라고 하는 것은 일단 앞에서 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 오케이 그러지말고 내가 예제를 만들어서 풀어보도록 하겠습니다. 엠엔이 10 12가 들어왔다고 가정을 하고 이렇게 흘러갑니다. 1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 9:9 10:10 1:11 2:12 3:1 4:2 5:3 6:4 7:5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 예를 들어 5:3 이라고 합니다. 그럼 10*5 = 50 입니다. 어떻게 풀어야 하는것이지? 아 잠깐만 이거 다 나머지로 계산하는 것이네, x%10=7입니다. 그럼 (x*10 + 7)%12 = 5 입니다. 그럼 10 20 30 40 50 60 70 80 90 100 입니다. 먼저 나머지 7과 뒷자리는 맞출 수 있습니다. 앞자리를 맞춰야 합니다. 그리고 단서가 하나더 있습니다. 5 엑스를 12로 나누어서 5가 떨어지는 값을 찾으면 됩니다. 음. 일단 오케이요. 어떻게 하는지 감을 잡았습니다. 예를 10 12 7 5 넣고 풀어보도록 하겠습니다. 숫자를 늘려가면서 12로 나누어보도록 하겠습니다. 포문에서 나오는 조건을 어떻게 두어야 할가요? M = 40000 이라고 가정하면 10 12 10 12 인데 10과 12의 최소공배수이군요. 오케이요. 최소공배수를 구하면 됩니다. 40000,39999 의 최소 공배수는 */ #include <iostream> using namespace std; int M, N, x, y; int ans; bool check = false; void problemIn() { cin >> M >> N >> x >> y; // 10 12 7 5 } int EU(int x, int y) { int n; while (1) { n = x%y; if (n == 0) return y; x = y; y = n; } } void solve() { int gcm, lcm; ans = 0; check = false;
gcm = EU(M, N); lcm = M*N / gcm;
for (int i = 0; ans <= lcm ; i++) { ans = M*i + x; if (ans % N == y) { check = true; break; } } if (check) { cout << ans << endl; } else { cout << -1 << endl; } } int main(void) { int T; cin >> T; for (int i = 0; i < T; i++) { problemIn(); solve(); } return 0; } |
안돌아가는 코드. 왜 안돌아가는지 확인해봐야지. 그리고 유클리디안 방법을 사용해서 최대공약수와 최소공배수를 찾는 것에 대해서 알 필요가 있습니다. |
한 문제가지고 2시간을 넘기지 않습니다. 이것에 대해서 패스하도록 하겠습니다. 다시 풀어볼 문제입니다. |