6064 카잉달력
알고리즘(수학)
1
2
3
4
5
6
7
8
1. n 을 M과 N으로 나누었을때 나온 수가 x와 y 이면 된다.
단, 나누었을때 나오는 수는 0~M-1 or N-1인데 문제에선 1~M, 1~N 까지이므로 이걸 고려해야한다.
2. 하나씩 증가시켜가면서하면 너무 오래걸리니, M과 N 중 더 큰수를 더하는 수로 삼고, 그것과 연결된 수부터 시작한다(M-x, N-y)
ex) 10 12 3 4 이면 4부터 시작하여 12씩 더함
각 단계의 수를 10과 12로 나누어서 3과 4가 나오면 가능한 것.
3. 이때 M과 N이 같을 경우 x, y이 다르게 나오면 바로 -1 을 출력하도록 해야 틀리지 않는다.
4. 2를 최소공배수 이하일때까지만 검사하는데, 최소공배수 구하긴 귀찮으므로 M*N 이하일 때까지 검사하자.
최대 N 번 검사하는게 고작이고, N 은 최대 4만이다. (M < N일때)
코드
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
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
int M, N, x, y;
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> M >> N >> x >> y;
int result = 0, lap, start;
if (M > N) {
lap = M;
start = x;
}
else if(M < N) {
lap = N;
start = y;
}
else if (x != y) {
cout << -1 << endl;
continue;
}
else {
lap = N;
start = y;
}
while (start <= M * N) {
int t1 = start % M == 0 ? M : start % M;
int t2 = start % N == 0 ? N : start % N;
if (t1 == x && t2 == y) {
result = start;
break;
}
start += lap;
}
if (result == 0)
cout << -1 << endl;
else
cout << result << endl;
}
}