[C++] 카잉 달력 (백준 6064번)

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

 

#include <iostream>
using namespace std;

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

    int t;
    cin >> t;

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

        int k = 0;
        bool psb = false;
        for (int i = 0; i < 40001; i++) {
            k = m * i + x;
            if ((k - y) % n == 0) {
                psb = true;
                break;
            }
        }

        if (psb) cout << k << '\n';
        else cout << -1 << '\n';
    }
}

잘 모르겠어서 태그를 깠더니 난생 처음 보는 중국인의 나머지 정리..?? 이게 뭐야 하면서 질문 게시판을 슬쩍 보니 중국인의 나머지 정리를 쓰지 않아도 풀 수 있는 것 같아서 다시 돌아와 스스로 풀어보았다. 

우선 다음과 같이 식을 세웠다.

m * a + x = n * b + y = k

여기서 a와 b는 어떤 수가 와도 상관이 없다. 다시 말해, k - x가 m으로 나누어 떨어져야 하고, 동시에 k - y도 n으로 나누어 떨어져야 한다. 그래서 나는 a를 0부터 40000까지 하나씩 대입해보면서 가능한 k가 있는지 찾았다. 찾아지면 그 즉시 종료하고, 40000까지 대입해봐도 찾을 수 없었다면 -1을 출력한다. (AC)