給定 A 和 B，在 C++ 中求 X = P*A + Q*B 的最小正整數解

問題陳述

給定 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

Narendra Kumar

更新於：2019年11月22日

135 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習