C++에서 ax − by = 0을 만족하는 x와 y의 최솟값 찾기

두 개의 값 a와 b가 주어졌을 때, ax − by = 0을 만족하는 x와 y를 찾는 것이 목표입니다. 예를 들어 a = 25이고 b = 35라면, x = 7, y = 5가 정답이 됩니다.

접근 방법

ax − by = 0이라는 것은 곧 ax = by, 즉 양변의 값이 같다는 의미입니다. 따라서 x와 y의 최솟값을 구하려면 a와 b의 최소공배수(LCM)를 계산하면 됩니다. 최소공배수는 a의 배수이면서 동시에 b의 배수가 되는 가장 작은 수이므로, 양변을 같게 만들 수 있는 가장 작은 값입니다.

최소공배수를 구했다면 x = LCM ÷ a, y = LCM ÷ b로 각 값을 계산할 수 있습니다. 이때 최소공배수는 다음 공식처럼 최대공약수(GCD)를 이용해 효율적으로 구할 수 있습니다.

LCM(a, b) = (a × b) / GCD(a, b)

예제 코드

#include<iostream>
#include<algorithm>
using namespace std;
void getSmallestXY(int a, int b) {
   int lcm = (a * b) / __gcd(a, b);
   cout << "x = " << lcm / a << "\ny = " << lcm / b;
}
int main() {
   int a = 12, b = 26;
   getSmallestXY(a, b);
}

실행 결과

x = 13
y = 6

동작 원리

a = 12, b = 26인 경우를 살펴보겠습니다. 먼저 GCD(12, 26) = 2이므로, LCM = (12 × 26) / 2 = 156이 됩니다. 이후 x = 156 / 12 = 13, y = 156 / 26 = 6을 계산할 수 있습니다. 실제로 12 × 13 = 156이고 26 × 6 = 156이므로 ax = by 조건이 성립하며, 최소공배수의 정의에 따라 이보다 더 작은 해는 존재하지 않습니다.