[백준-cpp] 6064. 카잉달력

1. 문제핵심

• 종말의 날 <M, N>까지 <x, y>의 날짜가 몇 번째 날인 지 / 없다면 -1 출력
• 종말의 날<M, N>는 M과 N의 최소공배수
• M, N의 범위는 4만 이하이기 때문에 최악의 경우 4만*4만번 째 날이 종말의 날이 될 수 있다.
• day를 1씩 증가시키면서 확인하면 연산 횟수가 1억번을 초과하기 때문에 시간 제한에 걸려버린다.
• 따라서 조건으로 주어지는 x 혹은 y를 고정값으로 두고 M 또는 N 만큼 day를 증가시켜 일치하는 날이 존재하는 지 확인한다.
• 예를 들어, x를 시작일(=day)로 두고 day += m 씩 날짜를 건너뛰면서 그 날의 y'값이 조건의 y값과 일치하는 지 확인하면 된다.

 

2. 해결

#include <bits/stdc++.h>

using namespace std;

int t;

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> t;

    while (t--)
    {
        int m, n, x, y;
        cin >> m >> n >> x >> y;

        int doom = m * n / __gcd(m, n);

        int day = x;
        while (day <= doom)
        {
            if ((day - 1) % n + 1 == y)
                break;

            day += m;
        }

        if (day > doom)
            cout << -1 << '\n';
        else
            cout << day << '\n';
    }

    return 0;
}