6064 카잉 달력

www.acmicpc.net/problem/6064

6064번: 카잉 달력

육십갑자의 확장판 문제.

M = 10, N = 12 인 경우는 육십갑자의 방식과 같다. (10개의 천간, 12개의 지지)

총 경우의 수는 M과 N의 최소공배수 만큼이다.

따라서 육십갑자의 모든 경우의 수는 10과 12의 최소공배수인 60이다.

 

처음에는 최소공배수를 구해서 그만큼 돌리다가 안나오면 -1, 나오면 출력을 하려고 했으나...

그냥 배열로 중복을 체크하면서, x는 고정시킨 채 y가 나오는 해를 구할 때까지 m년만큼 지내고 중복이 발생하면 바로 -1을 출력하는 방식으로 답을 구했다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--)
    {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
        x--; y--;
        vector<bool> check(n, false);
        int tmp = x%n, cnt = x+1;
        while(1)
        {
            if(check[tmp])
            {
                cout << -1 << endl;
                break;
            }
            check[tmp] = true;
            if(tmp == y)
            {
                cout << cnt << endl;
                break;
            }
            cnt += m;
            tmp = (tmp+m)%n;
        }
    }
    return 0;
}