6064번

6064번 - 카잉 달력

규칙을 찾아서 풀면 간단하게 풀 수 있는 문제였다.

처음에 나는 규칙을 찾았지만, 같은 규칙을 아주 복잡하게 구해서 문제를 푸는데 어려움을 겪었다.

규칙을 간단하게 말하면,

둘 중 하나의 숫자에 맞춰놓고, 칸을 옮겨가면서 있는지만 확인하면 된다. 이때 MAX값은 두 길이의 최소공배수가 된다.

그래서 최소공배수는 유클리드 호제법을 이용한 최대공약수를 이용해서 풀었다.

(유클리드 스펠링이 사실 uclid 가 아님)

<정답 코드>

#include<iostream>
#include<string.h>
 
using namespace std;
 
int uclid(int x, int y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return uclid(y, x % y);
    }
}
int main()
{
    int tc;
    scanf("%d", &tc);
    while (tc--)
    {
        int n, m, n1, m1;
        scanf("%d%d%d%d", &n, &m, &n1, &m1);
        int MAX = n*m / uclid(n, m);
        int x = 1, y = 1;
        int cnt = 1;
        while (cnt<=MAX)
        {
            if (x < n1)
            {
                x++; y++; cnt++;
                if (x > n)x -= n;
                if (y > m)y -= m;
            }
            
            if (x == n1 && y!=m1)
            {
                cnt += n;
                y += n;
                while (y > m)
                {
                    y -= m;
                }
            }
 
            if (x == n1 && y == m1)
            {
                break;
            }
        }
 
        if (cnt > MAX)
        {
            cnt = -1;
        }
 
        printf("%d\n", cnt);
    }
 
    return 0;
}