6064번: 카잉 달력

문제링크

C++

#include <iostream>

using namespace std;

int T, M, N, x, y;

int ret;

int    gcd(int a, int b){
    while (b > 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return (a);
}

int    lcm(int a, int b){
    return (a * b / gcd(a, b));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;

    for (int i = 0; i < T; i++){
        cin >> M >> N >> x >> y;
        ret = -1;
        int tmp = x;

        int cnt = x;

        for (int j = 0; j < N; j++){
            int yy;
            if (tmp % N == 0)
                yy = N;
            else
                yy = tmp % N;
            if (yy == y)
                break;
            cnt += M;
            tmp = yy + M;
        }
        if (cnt < lcm(M, N))
            cout << cnt << "\n";
        else
            cout << -1 << "\n";
    }
}

• x값을 기준으로 카운트를 M씩 증가시켜 가면서 원하는 숫자가 있는지 체크하는 방식
• 카운트의 upper bound는 M과 N의 최소공배수
  • 유클리드 호제법 사용
• $O(lcm(M, N)) / M$