[백준 BOJ][C++]6064번 카잉 달력 풀이: 브루트 포스

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

6064번: 카잉 달력

 

 

 

[풀이 과정]

 

1. 멸망년도인 m과 n의 최소공배수를 구한다.

 

2. <x:y> 로 표현되는 해 i를 x값으로 초기화 한다. 

 

3. (i - 1)%n + 1 == y를 만족하는지 검사한다.

 

4. 최소공배수에 도달하거나 위 조건을 만족할 때까지 i 에 m 값을 더해 3~4 과정을 반복한다. 

 

5. i가 최소 공배수보다 크다면 유효하지 않은 해이고, 그렇지 않다면 i를 출력한다. 

 

 

#include<iostream>
#include<algorithm>

using namespace std;

int gcd(int a, int b) {
	
	if (a < b) {
		int temp = a;
		a = b;
		b = temp;
	}

	int r = a % b;

	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

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

int main(void) {
	int t;
	int n, m, x, y;

	cin >> t;

	while (t > 0) {

		cin >> m >> n >> x >> y;

		int i;
		bool flag = false;
		int limit = lcm(m, n);

		for (i = x; i <= limit; i += m) {
			if ((i - 1) % n + 1 == y) {
				flag = true;
				break;
			}
		}

		if (flag) {
			cout << i << endl;
		}
		else {
			cout << -1 << endl;
		}

		t--;
	}
    
    return 0;
}