취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6064번 문제인 카잉 달력이다.
문제는 아래 링크를 확인하자.

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

첫 번째 해부터 1년씩 시뮬레이션을 해보는 것은 매우 비효율적일 것이다. 최악의 경우 40000*39999번이라는 매우 많은 연산을 해야한다. 그러니 다음과 같은 관찰을 해보자.

현재 년도가 <A:B>일 때, M년이 지난 뒤의 년도는 <A:(B+M)%N>이 될 것이다. (단, (B+M)%N이 0이 된다면 <A:N>이 될 것이다.)

또한, 현재 년도가 <A:B>일 때, N년이 지난 뒤의 년도는 <(A+N)%M:B>이 될 것이다. (단, (A+N)%M이 0이 된다면 <A:B>이 될 것이다.)

위 관찰을 이용하면, 반복문을 이용하여 문제를 간단히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

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

	int T; cin >> T;
	while (T--) {
		int ans = 1;
		int N, M, x, y; cin >> N >> M >> x >> y;
		x--, y--;
		ans += x;
		int a = x, b = x % M;
		int cnt = M;
		while (cnt--) {
			if (b == y) break;
			b = (b + N) % M;
			ans += N;
		}
		if (b == y) cout << ans << '\n';
		else cout << -1 << '\n';
	}
}