💡 브루트포스 알고리즘/중국인의 나머지 정리/수학/정수론
Memory 2056KB Time 108ms Code Length 547B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
using namespace std;
int N, M, x, y;
void init() {
cin >> N >> M >> x >> y;
}
int solved() {
int cnt = x; // x로 맞춰놓기
int ny = x % M;
if (ny == 0) ny = M;
int visited[40001] = { 0 };
visited[ny] = 1;
while (1) {
if (ny == y) {
return cnt;
}
ny = (ny + N) % M;
if (ny == 0) ny = M;
cnt += N;
if (visited[ny] == 1) break;
visited[ny] = 1;
}
return -1;
}
int main() {
int t = 0;
cin >> t;
for (int tc = 0; tc < t; tc++) {
init();
int result = solved();
cout << result << endl;
}
}
init 함수에서는 N, M, x, y 값을 입력받는다. solved 함수에서는 x부터 시작하여 N씩 증가시켜 y와 일치할 때까지 반복하며, 중복 방문을 체크하면서 이동한다. 만약 y와 일치하면 이동 횟수를 반환하고, 중복 방문이 발생하면 -1을 반환한다. main 함수에서는 테스트 케이스 수를 입력받고 각 테스트 케이스에 대해 init 함수로 초기화한 후 solved 함수를 호출하여 결과를 출력한다.
