C++에서 X = P*A + Q*B로 표현 가능한 최소 양의 정수 X 구하기

문제 설명

두 정수 A와 B가 주어졌을 때, 다음 식을 만족하는 최소 양의 정수 X를 구하는 문제입니다.

X = P*A + Q*B

여기서 P와 Q는 0을 포함하여 임의의 양의 정수 또는 음의 정수 값을 가질 수 있습니다.

예시

A = 2, B = 4라고 할 때, 답은 2입니다.

접근 방법

이 문제는 베주 항등식(Bézout's identity)을 이용하면 간단히 해결할 수 있습니다. 베주 항등식에 따르면, P*A + Q*B 형태로 표현할 수 있는 최소 양의 정수 값은 바로 A와 B의 최대공약수(GCD)와 같습니다.

따라서 복잡한 탐색 없이 A와 B의 GCD만 계산하면 곧바로 답을 구할 수 있습니다. GCD는 재귀적으로 구현되는 유클리드 호제법(Euclidean algorithm)을 사용해 효율적으로 계산할 수 있습니다.

구현 코드

#include <iostream>
using namespace std;
int getGcd(int a, int b) {
   if (a == 0) {
      return b;
   }
   return getGcd(b % a, a);
}
int main() {
   cout << "Answer = " << getGcd(2, 4) << endl;
   return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Answer = 2

정리

P와 Q가 모든 정수 값을 가질 수 있다는 조건에서, P*A + Q*B로 만들 수 있는 가장 작은 양의 정수는 항상 gcd(A, B)입니다. 따라서 이 문제의 시간 복잡도는 유클리드 호제법의 복잡도인 O(log(min(A, B)))로 매우 효율적입니다.