문제 설명
A와 B의 값이 주어지면 X =P*A + Q*B 방정식에서 얻을 수 있는 X의 최소 양의 정수 값을 찾으십시오. 여기서 P와 Q는 0 또는 양 또는 음의 정수일 수 있습니다.
예시
A =2, B =4이면 답은 2가 됩니다.
알고리즘
- P*A> P*B 및 P*A – P*B가 최소 양의 정수가 되도록 P와 Q를 찾아야 합니다.
- 이 문제는 두 숫자의 GCD를 계산하여 쉽게 해결할 수 있습니다.
예시
#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