백준 6064 : 카잉 달력

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

6064번: 카잉 달력

문제에서는 각 년도를 <x:y>와 같은 형식으로 표현하고, 첫 번째 해를 <1:1>, 두 번째 해를 <2:2>로 표현합니다. <x:y>의 다음 해를 표현한 것을 <x':y'>라 할 때, x < M이면 x'=x+1이고, 그렇지 않으면 x'=1입니다.

 

즉, x는 M과 같아지면 1이 되고, y는 N과 같아지면 1이 됩니다. 네 개의 정수 M, N, x, y가 주어질 때, <M:N>이 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 문제였습니다.

 

모든 경우를 다 해보기에는 N과 M의 범위가 너무 커서 x를 고정시켜놓고 문제를 해결했습니다. 

 

[소스코드]

 

#include<cstdio>
 
int tc, m, n, x, y;
 
int solve(void) {
    // x와 y를 1씩 감소시키면 i번째 해를 M으로 나눈 나머지는 x,
    // N으로 나눈 나머지는 y를 만족하게 됩니다
    x -= 1, y -= 1;
 
    // i를 x부터 m씩 더해나갑니다(i를 x로 나눈 나머지는 m)
    for (int i = x; i <= n * m; i += m) {
 
        // 그 i를 n으로 나눈 나머지도 y를 만족하면
        if (i % n == y) return i + 1;
    }
    return -1;
}
 
int main(void) {
 
    scanf("%d", &tc);
    for (int t = 0; t < tc; t++) {
        scanf("%d%d%d%d", &m, &n, &x, &y);
        printf("%d\n", solve());
    }
    return 0;
}