给定 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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习