백준 6064 카잉 달력 (C++)

6064번: 카잉 달력

최소공약수를 이용하여 해결한 문제이다. 문제를 보면 x나 y가 M, N을 넘어가면 1로 돌아간다고 되어있다. 즉 x를 M으로 나눈 나머지가 x가 된다는 뜻이다. y도 마찬가지이다. 달력의 마지막 해는 두 수의 최소공배수를 의미하므로 먼저 최소공배수를 구해준다. x를 시작으로 최소공배수까지 M을 더해주며 반복문을 돌아준다. x=4, M=10이라면 4, 14, 24 ...가 된다. 해당 x일때의 y를 구해주고 찾아야되는 y와 일치한다면 해당 해를 출력해준다.
생각보다 어려웠던 문제였다. 최소 공배수는 생각을 해냈지만 해당 해를 구하는 로직을 떠올리지를 못했다.

#include <iostream>
#include <algorithm>

using namespace std;

int M, N, x, y;

int gcd(int a, int b) {
	if (a % b == 0) {
		return b;
	}

	return gcd(b, a % b);
}

int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

void solution() {
	int result = -1;

	for (int i = x; i <= lcm(M, N); i += M) {
		int ny = i % N;

		if (ny == 0) {
			ny = N;
		}

		if (ny == y) {
			result = i;
			break;
		}
	}

	cout << result << endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;

	while (T--) {
		cin >> M >> N >> x >> y;

		solution();
	}
	
	return 0;
}