[C++][백준 6064] 카잉 달력

문제

접근 방법

x와 y의 값이 어떤 과정을 통해 나왔는지를 살펴봐야 한다.
x와 y의 값은 각각 M, N으로 나머지 연산을 하여서 구해진 것이다.
다시 k번째 해를 구하는 과정도 M과 N을 통해서 구할 수 있는 것이다.

코드

#include <iostream>
using namespace std;
int T, M, N, x, y;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> M >> N >> x >> y;

        while (true)
        {
            if (x == y)
            {
                cout << x << "\n";
                break;
            }
            else if (x > M * N)
            {
                cout << -1 << "\n";
                break;
            }

            if (x < y)
            {
                x += M;
            }
            else
            {
                y += N;
            }
        }
    }
    return 0;
}

풀이

결국 x와 y는 k번째 해에 대해서 M과 N의 나머지인 것이다. 바꿔 말하자면 원래는 같은 수였다. 즉 x와 y가 정상적으로 M, N의 나머지 연산으로 만들어진 값이면 x와 y에 M, N을 반복적으로 더하면 같은 수가 나올 것이다.

만약 M*N에 해당하는 값보다 크다면 카잉 달력의 마지막 해를 넘는 값이므로 -1을 출력하면 된다.