백준 6064 카잉 달력

문제 링크: https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

i를 y로 시작해서 n씩 증가시키면서 for문을 돌리다가 i를 m으로 나눈 나머지가 x일때의 i값이 답이다. 다시 말해서, 년도의 두번째 숫자를 고정시켜놓고, 첫번째 숫자가 x일때의 i값이 답이 되는것이다. 이렇게 고정시키지 않고 i를 1씩 증가시키면서 for문을 돌리면 시간복잡도가 O(N^2)가 되는데 N이 40000이므로 시간내에 돌아갈수가 없다.

#include <bits/stdc++.h>
using namespace std;
 
int solve(int m, int n, int x, int y) {
    for(int i = y; i <= m * n; i += n) {
        if((i - 1) % m + 1 == x)
            return i;
    }
    return -1;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while(t--) {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
        cout << solve(m, n, x, y) << '\n';
    }
    return 0;
}