BOJ)6064 카잉 달력

문제: icpc.me/6064

n년도를 x:y로 표현할 때 n+1년도는 if(x==m) x=1 else x=x+1 if(y==n) y=1 else y=y+1 로 표현할 때 x:y가 몇년도인지 찾는 문제이다.

처음에 단순하게 시뮬레이션을 돌려봤으나 시간초과를 받아서 문제를 다시 보니 M과 N이 40000씩이므로 O(N*M)의 시뮬레이션으로는 해결할 수 없는 문제였다.

그래서 수식을 사용하여 for(int i=0;i<=n;i++) (m*i+(x-y)) 가 n으로 나누어 떨어질 때 m*i+x 가 답이된다.

이때 원래 세상의 종말이 온다는 마지막 해 이후에는 정의되지 않으므로 m과 n의 LCM 까지만 돌리면 된다.

#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;
int t, m, n, x, y, r, a;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d%d", &m, &n, &x, &y);
        r = INF;
        for (int i = 0; i <= n; i++) {
            if (!((m*i + (x - y)) % n)) {
                r = m*i + x;
                break;
            }
        }
        for (int i = 0; i <= n; i++) {
            if (!((m*i + (m - n)) % n)) {
                a = m*i + m;
                break;
            }
        }
        if (r == INF || a < r)
            printf("-1\n");
        else
            printf("%d\n", r);
    }
    return 0;
}