1 <= M N <= 40,000 , 1<= x<= M, 1<=y <=N 범위의 M, N, x, y가 문제의 입력으로 주어집니다.
<M : N> 이 마지막 해이며, <x : y> 는 맞춰야 하는 해입니다.
예를 들어 이 달력은 M = 3 , N = 2, x = 2, y = 1라 하였을 때,
<1 : 1>
<2 : 2>
<3 : 1>
<1 : 2>
<2 : 1>
<3 : 2>
순서로 증가하며, < 3 : 2 > 해가 마지막 해이고, 정답은 <2 : 1> 가 되는 해인 4번째 해입니다.
즉 < x : y > 해가 몇 번째 되는 해인지 맞추는 문제입니다.
🔔 Kick Point :
x의 숫자에 고정 시켜둔 뒤 y 숫자를 증가 시키면 더욱 편리하게 구할 수 있습니다.
하지만 여기서 중요한 점으론 언제까지 반복 할 수 있느냐 입니다.
마지막 해의 <M : N> 보다 큰 해가 되었을 때는 해를 증가하는 것을 멈춰야 하기 때문에, M , N의 LCM(최소공배수)을 구하면 범위를 알 수 있게 됩니다.
따라서 최소공배수를 구하는 공식으론
최소공배수(LCM) = (M * N) / 최대 공약수 (GCD) 를 사용하면 됩니다.
여기서 최대 공약수를 구하는 공식으론 유클리드 호제법을 사용합니다.
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
유클리드 호제법이란 최대공약수를 쉽게 알아내는 알고리즘으로
a > b 인 조건의 두 수가 있을 때, a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b와 r의 최대 공약수와 같다는 성질을 이용한 것입니다.
예시로 1071과 1029의 최대 공약수를 구하면
1071 % 1029 = 42 (1071은 1029로 나누어 떨어지지 않기에 계속 진행한다.)
1029 % 42 = 21 (1029은 42로 나누어 떨어지지 않기에 계속 진행한다.)
42 % 21 = 0 ( 42는 21로 나누어 떨어지기 때문에 최대 공약수는 21이다.)
즉 최대 공약수는 21이 된다.
🔔 Code :
#include <iostream>
using namespace std;
// 최대 공약수 공식 (유클리드 호제법)
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
// 최소 공배수 공식
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
int main() {
int m, n, x, y, t, k = 0; // k = result
cin >> t;
while (t--) {
int _m = 0;
int _lcm;
cin >> m >> n >> x >> y;
// 최소공배수 대입
if (m >= n) _lcm = lcm(m, n);
else _lcm = lcm(n, m);
k = x; // default 값
while (true) {
int tmp = (x + m * _m) % n;
// 구할 조건
if (tmp == y) break; // % 할때 0인것을 추가해야한다.
else if (tmp == 0) { if (n == y) break; }
k += m;
_m++;
// 아닐 조건
if (k > _lcm){
k = -1;
break;
}
}
cout << k << "\n";
}
}
// 최소공배수 -> 두 자연수의 곱 / 최대 공약수(유클리드 호제법)
// GCD ( Greatest Common Divisor)
// LCM ( Least Common Multiple )