[C++] 백준 6064번 카잉 달력

카잉 달력<M:N>에서 <x:y>년을 찾을 때 몇년이 걸리는지 찾는 문제입니다.

카잉 달력은 <a:b>가 있을 때 1년이 지나면
a + 1
b + 1이 됩니다.
만약 a가 M이 되었다면 다시 1로 돌아가며
b 또한 N이 되면 1로 돌아가는 규칙을 가졌습니다.

이 때 <M:N> 카잉달력에서 <x:y>는 몇년째에 오는지 찾아야합니다.

x는 M * i + x 때마다 오는것을 확인 할 수 있습니다.

ex)
M = 10
N = 12
x = 3
y =9

x가 3인 경우는 
3년
13년
23년
33년
....

y가 9인 경우는
9년
21년
33년
45년
....

먼저 최소공배수를 찾아서
x가 가능한 년을 찾고 그 년도에
y가 맞는지 확인하여서 문제를 풀었습니다.

#include <iostream>
#include <cstring>
using namespace std;

void printResult(int x)
{
	if (x != 0) {
		cout << x << endl;
	}
	else {
		cout << "-1" << endl;
	}
}

int gcd(int a, int b)
{
	int c;
	while (b != 0)
	{
		c = a % b;
		a = b;
		b = c;
	}
	
	return a;
}

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

int main(int argc, char *argv[])
{
	int testcase;
	int m, n, x, y;
	int endDay;
	int count;

	cin >> testcase;

	while (testcase--) {
		count = 0;

		cin >> m >> n >> x >> y;
		
		endDay = lcm(m, n);

		for (int i = 0; (m * i) + x <= endDay; ++i) {
			int t = ((m * i) + x) % n;
			if (t == 0) {
				t = n;
			}

			if (t == y) {
				count = (m * i) + x;
				break;
			}
		}

		printResult(count);
	}

	return 0;
}