(C++) 6064번 - 카잉 달력

문제 링크 : https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

문제 풀이

문제에 나온 예시를 들어보면 M = 10이고 N = 12일 때 첫 번째 해는 <1:1>, 11번째 해는 <1:11>, 13번째 해는 <3:1>, <10:12>는 마지막인 60번째 해를 나타낸다.

이들의 규칙을 찾아보면 n번째 해는 <n % M, n % N> 임을 알 수 있다.

그리고 당연히 마지막 해는 규칙에 의해 최소공배수 즉 60번째 해임을 알 수 있다.

이를 이용하여 풀이하였다.

#include <iostream>

using namespace std;

int T, m, n, x, y;

int gcd(int m, int n){
    if(m == 0) return n;
    else return gcd(n%m, m);
}

int lcm(int m, int n){
    return m / gcd(m, n) * n;
}

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

    cin >> T;
    while(T--){
        cin >> m >> n >> x >> y;
        if(m==x) x = 0;
        if(n==y) y = 0;
        int upper = lcm(m,n);
        bool flag = false;
        for(int i = x; i <= upper; i += m){
            if(i == 0) continue; // m==x, n==y일 경우에 최소공배수 대신 0을 출력하지 않게 하기 위함
            if(i%n == y){
                cout << i << "\n";
                flag = true;
                break;
            }
        }
        if(!flag) cout << -1 << "\n";
    }
}