백준 6064 - 카잉 달력

문제

 

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

 

풀이

 

브루트포스로 해결하면 시간초과가 발생한다. 먼저 x를 맞춰주고 그 후에 y를 찾아줘야 한다. 

1. x는 M만큼 증가를 한다. 따라서 x = x + M이 된다.

2. y는 x에서 N을 나눴을 때 나머지 값이 된다. 따라서 y = x % N이 된다. 하지만 x가 1부터 초기화가 되고 나머지 연산은 0부터 시작되기 때문에 y = (x-1)%N + 1이 된다.

 

이 과정은 달력의 마지막 날 까지 가능한데, 달력의 마지막 날은 M과 N의 최소공배수 값이 된다. 따라서 x 값이 마지막 날을 넘어가면 -1을 출력하면 된다.

 

 

코드

 

#include <iostream>
 
using namespace std;
 
int T;
 
int gcd(int a, int b)
{
    while (b)
    {
        int r = a % b;
        a = b;
        b = r;
    }   
    return a;
}
 
int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> T;
 
    int M, N, x, y;
    while (T--)
    {
        cin >> M >> N >> x >> y;
        int result = x;
        int max = lcm(M, N);
        int t;
        do
        {
            t = (result - 1) % N + 1;
            if (t == y) break;
            result += M;
        } while (result <= max);
        cout << (result < max ? result : -1) << '\n';
    }
 
    return 0;
}