[Silver 1] 6064 카잉달력

https://www.acmicpc.net/problem/6064

 

카잉달력은 <1:1>에서 <M:N>까지 존재하며, <M:N>해에는 멸망의 해가 된다.

또한 <1:1>의 다음해는 x < M인 경우 x' = x + 1이 되고, y < N인 경우 y' = y + 1이 된다.

따라서 M = 10, N = 12인 경우 

<1:1>, <2,2>, <3,3>, <4,4>, <5,5>, <6,6>, <7,7>, <8,8>, <9,9>, <10, 10>, <1, 11>, ...이 된다.

 

카잉 달력의 51번째 해를 구할려면 어떻게 해야할까?

51번째 해는 M인 10이 5번 들어가고 그 후 1해가 지나가면 51번째 해가된다. ( x = 1 )

마찬가지로 N인 12가 4번 들어가고 그 후 3해가 지나가면 51번째 해가된다. ( y = 3 )

 

멸망해는 M과 N이 동시에 들어가는 최소공배수가 된다.

위 조건대로 멸망해의 최소공배수를 구하면 60이 된다.

 

 

먼저 예제의 경우를 보자

10

12

3

9

i = 3

i = 13

i = 23

i = 33

 .....

이런식으로 for문을 돌게 되는데 이 때 N값 즉 12로 나눈 값이 y 값 9가 되면 i의 값은 result가 된다.

3 % 12 = 12

13 % 12 = 1

23 % 12 = 11

33 % 12 = 9 ( == y)

이므로 33값이 i값이 된다.

 

그러나 다음은 어떨까 

1

1

1

1

이 경우 (i = 1) % (N=1) = 0이 되어버려 result값으로 -1 을 출력할 것이다.

그러나 실제 정답은 1 이어야 한다.

그러므로 N == y일 때를 따로 고려해야한다.

왜냐하면 N = 9 y = 9라고 가정했을 때 어떠한 값을 9로 나누었을 때 나머지로 9가 나올 수 없기 때문이다.

그럼 N == y이므로 result도 i 값인1로 하면 될까?

여기선 가능하겠지만 다음은 다르다

10

9

3

9

같은 방법으로

3 % 9 = 3

13 % 9 = 4

23 % 9 = 5

33 % 9 = 6

43 % 9 = 7

53 % 9 = 8

63 % 9 = 0 (answer)

N 과 y값이 서로 같으므로 나머지는 절대 9가 나올수 가 없다.

이럴 때의 정답은 나머지가 0일 때이다

즉 N==y 이고 i%N = 0이면 i값이 result가 된다.

 

 

#include <iostream>
using namespace std;
 
int gcd(int a, int b){ // 최대 공약수
    if(b==0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b){ // 최소 공배수
    return (a * b) / gcd(a, b);
}
int main(){
    int T;
    cin >> T;
    for (int t = 0; t < T; t++){
        int m, n, x, y;
        int result = -1;
        cin >> m >> n >> x >> y;
        int maxi = lcm(m, n); // 멸망해
        for (int i = x; i <= maxi; i+=m){
            int ny = i % n; // y값
            if(ny == 0) // 이때는 y가 최대값이 됨
                ny = n;
            
            if(ny == y){ // 정답
                result = i;
                break;
            }
        }
        cout << result << '\n';
    }
    return 0;
}