समस्या विवरण
A और B के मान दिए गए हैं, समीकरण X = P*A + Q*B में प्राप्त होने वाले X का न्यूनतम धनात्मक पूर्णांक मान ढूंढें। यहां P और Q शून्य या कोई भी धनात्मक या ऋणात्मक पूर्णांक हो सकते हैं।
उदाहरण
यदि A = 2 और B = 4 तो उत्तर 2 होगा।
एल्गोरिदम
- हमें P और Q ढूंढने होंगे जैसे कि P*A > P*B और P*A - P*B न्यूनतम धनात्मक पूर्णांक हो।
- इस समस्या को दोनों संख्याओं के 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
