C++で方程式 f(x, y) = z を満たす正の整数解をすべて求める方法

問題の概要

2つの引数 (x, y) を受け取る関数 f があると仮定します。この関数は単調増加関数であり、次の性質を持ちます。

• f(x, y) < f(x + 1, y)
• f(x, y) < f(x, y + 1)

つまり、x または y の値を大きくすると、必ず f の戻り値も大きくなります。このとき、入力として与えられた z に対して、f(x, y) = z を満たす正の整数 x、y の組み合わせをすべて求めるのが本記事の目的です。

解き方：全探索アプローチ

ここでは、最も理解しやすい全探索（ブルートフォース）の手法を採用します。変数 i を 1〜1000、変数 j を 1〜1000 の範囲で二重ループさせ、すべての組み合わせ (i, j) について f(i, j) と z が一致するかどうかを確認します。条件を満たすペアが見つかったら、それを結果リストに追加していきます。

サンプルコードの CustomFunction クラスには、関数の種類を表す id を渡します。

• id = 1：加算（f(x, y) = x + y）
• id = 2：乗算（f(x, y) = x × y）

このアルゴリズムの計算量は O(1000 × 1000) = O(n²) です。なお、関数が単調増加であるという性質を利用すれば、双方向ポインタ（two pointers）テクニックによって O(n) まで高速化できる点にも触れておきます。

実装例

以下は C++ による実装例です。実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
   cout << "[";
      for(int i = 0; i<v.size(); i++){
         cout << "[";
            for(int j = 0; j <v[i].size(); j++){
               cout << v[i][j] << ", ";
            }
            cout << "],";
      }
      cout << "]"<<endl;
}
class CustomFunction {
   int id;
   public:
   CustomFunction(int id){
      this->id = id;
   }
   int f(int x, int y){
      if(id == 1)
         return y + x;
      else if(id == 2)
         return y * x;
      return 0;
   }
};
class Solution {
   public:
   vector<vector<int>> findSolution(CustomFunction& c, int z) {
      vector  < vector <int > > ans;
      for(int i = 1; i <= 1000; i++ ){
         for(int j = 1; j <= 1000; j++){
            if(c.f(i,j) == z){
               vector <int> t;
               t.push_back(i);
               t.push_back(j);
               ans.push_back(t);
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   CustomFunction c(1);
   print_vector(ob.findSolution(c, 7));
}

入力

1
7

出力

[[1, 6],[2, 5],[3, 4],[4, 3],[5, 2],[6, 1]]

出力の解説

今回の入力では id = 1（加算）が指定されているため、f(x, y) = x + y として計算されます。z = 7 なので、「和が 7 になる正の整数のペア」、すなわち (1, 6)、(2, 5)、(3, 4)、(4, 3)、(5, 2)、(6, 1) の 6 組が出力されています。id = 2（乗算）を指定すれば、積が z になるペアを同様の手順で求められます。