[브루트포스] BOJ 6064 카잉달력 - 오답노트

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

6064번: 카잉 달력

- 문제 파악

각 각 M진수 N진수가 주어지고 입력으로 주어지는 각각의 나머지를 만족하는 자연수 출력, 출력할 수 없으면 -1 출력

 

- 나의 시도

https://www.acmicpc.net/problem/1476 (날짜 계산) 과 같이 접근 하지만 그러면 시간초과

 

- 정답

1. M진수 먼저 생각했을 때, 입력으로 주어지는 M진수에 대한 나머지를 만족하는 자연수를 구하는 점화식을 구한다.

2. 1번으로 인해 앞으로는 N진수만 고려하면됨

3. M*N 보다 큰 자연수 일때는 -1을 출력한다 (자연수가 M*N 이면 각 진수의 나머지는 0으로 문제에서 카잉의 마지막 달력이 되어 -1이 된다)

#include "bits/stdc++.h"

using namespace std;

int arr[40005];


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

    int T;
    cin >> T;

    while (T--)
    {
        int M, N, x, y;
        cin >> M >> N >> x >> y;

        int n = 0;

        fill(arr, arr + 40005, 0);

        while (1)
        {
            int ans = M * n + x;

            int Y = ans % N;

            if (Y == 0)
                Y = N;

            if (ans > M * N)
            {
                cout << "-1\n";
                break;
            }


            if (y == Y) // 해당해 
            {
                cout << ans << "\n";
                break;
            }

            n++;


        }

    }
}

 

<추가>

> 연립합동방정식 풀이

m 과 n 의 최소공배수의 주기 마다 다시 돌아온다.

그러므로 1일부터 최소공배수까지 날 중에서 나머지가 각각 x,y인 날을 찾는다.

하지만 위 방법으로 하면 시간초과이다.

 

그러므로 x인 날 부터 m일의 주기로 최소공배수까지 살피는데, 그중에서 n의 나머지가 y인 날만 찾는다.

#include "bits/stdc++.h"

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

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

        if (m == x) x = 0;
        if (n == y) y = 0;

        int nlcm = lcm(m, n);
        bool bflag = true;

        if (x == 0 && y == 0)
        {
            cout << nlcm << "\n";
            continue;
        }

        for (int i = x; i <= nlcm; i+=m)
        {
            if (i % m == x && i % n == y)
            {
                bflag = false;
                cout << i << "\n";
                break;
            }
        }

        if (bflag)
            cout << -1 << "\n";
    }


}