백준 6064 / 카잉 달력

정확히 1년전에 풀어봤던 문제.

그때는 막 공약수도 구하고 복잡하게 풀었던 거 같은데.

강의를 보니 꽤 쉽게 풀리는 문제였다.

우선 year를 1씩 늘려가며 푸는 방식은 m,n의 제한이 4만이기 떄문에 시간초과가 발생한다.

카잉달력에서 앞자리와 뒷자리를 1씩 빼본 것이다.

1을 뺴보니 정확히 눈에 띄는 특징이 생긴다.

23을 예로 들면, 23을 5로 나눈 나머지가 3이고 7로 나눈 나머지가 2, 즉 <3,2>가 됨을 알 수 있다.

이 패턴을 발견하면 쉽게 풀 수 있다.

코드 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
 
    cin >> testcase;
 
    while (testcase--) {
        int m, n, x, y;
        bool find = false;
 
        cin >> m >> n >> x >> y;
        x--;
        y--;
 
        for (int i = 0; i < n; i++) {
            int now = m * i + x;
            
            if (now%n == y) {
                find = true;
                cout << now + 1 << endl;
                break;
            }
 
        }
        if (find == false) {
            cout << -1 << endl;
        }
 
    }
 
}

ps. 여기서 x와 y를 1씩 뺴주지 않고, now도 1을 더하고 출력하지 않아도 테스트케이스의 답은 나오지만 틀린걸로 체크된다.

반례가 존재하나보다.