[BOJ 6064] 카잉 달력

접근 방법 : 저번에 풀었던 '날짜 계산' 문제와 유사하다. 똑같은 방법으로 풀려고 했지만 시간초과가 나서 당황했다. M과 N값의 범위가 40000이므로 처음부터 M*N 까지 탐색을 시도했다간 엄청난 연산 숫자에 시간초과가 난다. 따라서 더 효율적인 방법을 찾아야 했는데 내가 생각해낸 방법은 아래와 같다.

L번째 년도라고 했을 때  L = M*(몫) + x (주어진 x 값) 을 만족한다. 따라서 몫을 반복문을 증가시키면서 일단 x가 의미하는 L 번째 연도를 찾고 그 L번째 년도가 (L-y) / N 을 만족한다면 찾은 L 값이 정답이 된다. L의 범위는 최대 M*N을 넘지 않으므로 반복문을 M*N까지 돌려준다.

만약 L 값이 M*N 값을 넘게 되면 -1을 리턴한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
using namespace std;
int M, N, x, y;
 
int solve() {
    int i = 0;
    int A = 0;
    while (A <= M*N) {
        A = M*i + x;
        if ((A - y) % N == 0) { return A; }
        i++;
    }
    return -1;
}
 
int main() {
    int T;
    scanf("%d", &T);
    
    for (int i = 1; i <= T; i++) {
        
        scanf("%d %d %d %d", &M, &N, &x, &y);
        int ans = solve();
 
        printf("%d\n", ans);
    }
 
    return 0;
}