C++でax + by = nを満たすxとyを求める方法

この問題では、3つの整数値 a、b、n が与えられます。私たちのタスクは、ax + by = n を満たす x と y を見つけることです。

問題の理解

まず、具体例を見て問題を把握しましょう。

入力 : a = 4, b = 1, n = 5
出力 : x = 1, y = 1

この場合、4 × 1 + 1 × 1 = 5 となり、確かに方程式を満たしています。

解法のアプローチ

この問題に対するシンプルな解決策は、0 から n までの範囲で方程式を満たす値を順に探していくことです。これを実現するために、方程式を次のように変形します。

x = (n − by) / a
y = (n − ax) / b

x の候補を 0 から順に試し、残りの値が b で割り切れるかどうかを確認します。割り切れれば、それが y の値となります。方程式を満たす組み合わせが見つかればその値を出力し、最後まで見つからなければ「解は存在しない（no solution exists）」と表示します。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;

void findSolution(int a, int b, int n){
   for (int i = 0; i * a <= n; i++) {
      if ((n - (i * a)) % b == 0) {
         cout<<i<<" and "<<(n - (i * a)) / b;
         return;
      }
   }
   cout<<"No solution";
}

int main(){
   int a = 2, b = 3, n = 7;
   cout<<"The value of x and y for the equation 'ax + by = n' is ";
   findSolution(a, b, n);
   return 0;
}

コードの解説

関数 findSolution では、変数 i を 0 から i * a <= n を満たす範囲でインクリメントしながらループします。各反復において、(n − i * a) が b で割り切れるかどうかを剰余演算子 % で判定します。割り切れた場合は、i が x の値、(n − i * a) / b が y の値となるため、それらを出力して処理を終了します。ループが完了しても解が見つからなければ、「No solution」と出力します。

出力結果

The value of x and y for the equation 'ax + by = n' is 2 and 1

この例では a = 2、b = 3、n = 7 であるため、x = 2、y = 1 が 2 × 2 + 3 × 1 = 7 を満たす解として出力されています。