[algorithm] 백준 - 카잉 달력

이 문제는 시간 제한이 1초인 것에 유의해야하는 문제이다.

 

두 자연수의 최소 공배수까지 반복문을 돌며 나머지 값과 동일한 경우를 구하게 되면

40000 * 40000 이상의 연산은 1초를 넘게 되서 시간 초과가 난다.

 

참고로 최소 공배수까지 반복문을 도는 이유는,

최소 공배수를 기점으로 나머지가 0이 되기 때문에 x: y 또한 m: n이 될 것이므로,

그 이상의 수를 반복시킬 이유는 없어진다.

 

 

예를 들어 m:n = 10 : 12 일 경우, 최소 공배수는 60으로

x : y	k번째 해
10:12	60
1 : 1	61
10: 12	120
1: 1	121

60을 주기로 계속 반복되는 것을 관찰 할 수 있다.

 

그렇다면 어떻게 시간 제한을 1초 내로 줄일 수 있을까?

 

반복문은 굳이 최소 공배수까지 돌 필요가 없다.

 

for(int i = 0; (x * i + m) <= a * b / gcd; i++)

 

이 정도의 반복문을 돌면 된다.

 

(참고로 a * b / gcd는 최소 공배수를 의미한다.)

 

k 번째 해에 해당하는 k mod n은 y인지 보면되기 때문이다. 

 

for(int i = 0; (i*m+x) <= gcd * divideM * divideN; i++){
            if((i*m+x) % n == y || ((i*m+x) % n == 0 && y == n) ){
                cout << i*m + x << "\n";
                isPossible = true;
                break;
            }
        }

참고로 mod n = 0 일 경우 y는 n이라는 것을 유의해야한다.

 

따라서 코드는 이렇다.

//카잉 달력
#include <iostream>
using namespace std;

int uclid(int a, int b){
    while(a % b != 0){
        int n = a % b;
        a = b;
        b = n;
    }
    return b;
}

int main(void){
    int test;
    cin >> test;
    while(test--){
        bool isPossible = false;
        int m,n,x,y;
        cin >> m >> n >> x >> y;
        int gcd = uclid(m, n);
        int divideM = m / gcd;
        int divideN = n / gcd;
        for(int i = 0; (i*m+x) <= gcd * divideM * divideN; i++){
            if((i*m+x) % n == y || ((i*m+x) % n == 0 && y == n) ){
                cout << i*m + x << "\n";
                isPossible = true;
                break;
            }
        }
        if(!isPossible) cout << -1 << "\n";
    }
}