문제 개요
두 정수 p와 q가 주어졌을 때, 다음 두 조건을 동시에 만족하는 가장 작은 수 x를 찾는 것이 이번 문제의 목표입니다.
- q % x = 0 (x는 q를 나누어떨어지게 함)
- x % p = 0 (x는 p로 나누어떨어짐)
만약 어떤 수도 이 조건을 만족하지 않는다면 -1을 출력해야 합니다.
예시
p = 3, q = 66인 경우를 살펴보겠습니다.
66 % 3 = 0
3 % 3 = 0
두 조건을 모두 만족하므로 정답은 3입니다.
접근 방법 및 알고리즘
- 어떤 수 x가 위 조건을 만족한다면, x는 p의 배수이고 q는 x의 배수입니다. 따라서 q 역시 반드시 p로 나누어떨어져야 합니다. 즉, q % p = 0이 성립해야 합니다.
- 이 조건이 성립할 때 x가 될 수 있는 최솟값은 p와 q의 최대공약수(GCD)입니다. 반대로 q가 p로 나누어떨어지지 않는다면 조건을 만족하는 수는 존재하지 않으므로 -1을 반환하면 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int getMinValue(int p, int q) {
if (q % p == 0) {
return __gcd(p, q);
}
return -1;
}
int main() {
int p = 3;
int q = 66;
cout << "Minimum value = " << getMinValue(p, q) << endl;
return 0;
}
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
실행 결과
Minimum value = 3
정리
이 문제의 핵심은 배수 관계를 이용해 해답의 존재 여부를 먼저 판단한 뒤, 최대공약수를 활용해 최솟값을 즉시 도출하는 것입니다. 유클리드 호제법 기준 시간 복잡도는 O(log(min(p, q)))로 매우 효율적이며, 단순한 완전 탐색 없이도 빠르게 답을 구할 수 있습니다.