6064번: 카잉 달력

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

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;
int T, N, M, x, y;

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()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	freopen("input.txt", "rt", stdin);

	cin >> T; 

	for (int i = 0; i < T; ++i)
	{
		cin >> N >> M >> x >> y;

		if (N == x && M == y)
		{
			cout << LCM(N, M) << endl;
			continue;
		}

		int CurrentYear = x;
		while (true)
		{
			if (CurrentYear > N * M)
			{
				cout << -1 << endl;
				break;
			}

			if ((M == y && CurrentYear % M == 0) || CurrentYear % M == y)
			{
				cout << CurrentYear << endl;
				break;
			}
			
			CurrentYear += N;
		}
	}

	return 0;
}