C++로 합과 최대공약수(GCD)가 주어진 두 숫자 찾기

문제 개요

두 숫자 a와 b의 합(sum)과 최대공약수(GCD)가 주어졌을 때, 해당 조건을 동시에 만족하는 두 숫자를 찾는 문제입니다. 만약 그러한 숫자 쌍이 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어 합이 6이고 GCD가 2라고 가정해 보겠습니다. 이때 정답은 4와 2입니다. 실제로 4 + 2 = 6이고, gcd(4, 2) = 2이므로 두 조건을 모두 충족합니다.

접근 방법

GCD 값이 이미 주어져 있으므로, 두 숫자는 반드시 그 GCD의 배수여야 한다는 점을 활용합니다. 구체적인 풀이 단계는 다음과 같습니다.

첫 번째 숫자를 GCD(g)로 가정하면, 두 번째 숫자는 자연스럽게 합에서 GCD를 뺀 값, 즉 (sum − g)가 됩니다.
이렇게 구한 두 숫자의 실제 GCD가 주어진 g와 일치하는지 확인합니다. 또한 합과 GCD가 같아 두 번째 숫자가 0이 되어버리는 경우는 유효하지 않으므로 제외해야 합니다.
모든 조건을 만족하면 두 숫자를 출력하고, 그렇지 않다면 가능한 숫자 쌍이 존재하지 않는다는 의미로 -1을 출력합니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
using namespace std;

void printTwoNumbers(int s, int g) {
   if (__gcd(g, s - g) == g && s != g)
      cout << "first number = " << min(g, s - g) << "\nsecond number = " << s - min(g, s - g) << endl;
   else
      cout << -1 << endl;
}

int main() {
   int sum = 6;
   int gcd = 2;
   printTwoNumbers(sum, gcd);
}

코드 설명

__gcd()는 <algorithm> 헤더에 포함된 함수로, 유클리드 호제법을 기반으로 두 수의 최대공약수를 빠르게 계산해 줍니다.
__gcd(g, s - g) == g 조건은 가정한 두 숫자의 실제 GCD가 주어진 값과 일치하는지 검증합니다.
s != g 조건은 두 번째 숫자가 0이 되는 잘못된 경우를 걸러냅니다.
min(g, s - g)를 사용해 작은 수를 먼저 출력하여 결과의 일관성을 유지합니다.

실행 결과

first number = 2
second number = 4

합이 6이고 GCD가 2일 때, 프로그램은 조건을 만족하는 두 숫자인 2와 4를 올바르게 출력하는 것을 확인할 수 있습니다.