剰余問題

以下の問題は QUBO++ を使用して解決できます。 $x$ を最小の非負整数として求めよ。

$x$ を 3 で割ったときの余りが 2 であり、
$x$ を 5 で割ったときの余りが 3 であり、
$x$ を 7 で割ったときの余りが 5 となるような最小の非負整数 $x$ を求めよ。

3, 5, 7 は互いに素であるため、1周期内で $x$ を検索すれば十分である：

\[0\leq x \leq 3\times 5\times 7 -1\]

非負整数 $d_3$、$d_5$、$d_7$（商）を導入し、剰余条件を線形等式で書き換える：

\[\begin{aligned} x - 3d_3 &= 2 \\ x - 5d_5 &=3 \\ x - 7d_7 &= 5 \end{aligned}\]

これらの制約条件のもとで $x$ を最小化したい。上記の $x$ の範囲から、商変数を次のように制限できる：

\[\begin{aligned} 0&\leq d_3 \leq 5\times 7-1 \\ 0&\leq d_5 \leq 3\times 7-1 \\ 0&\leq d_7 \leq 3\times 5-1 \end{aligned}\]

QUBO++ プログラム

以下のプログラムはこの剰余問題の解 $x$ を求める：

#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"

int main() {
  auto x = 0 <= qbpp::var_int("x") <= 3 * 5 * 7 - 1;
  auto d3 = 0 <= qbpp::var_int("d3") <= 5 * 7 - 1;
  auto d5 = 0 <= qbpp::var_int("d5") <= 3 * 7 - 1;
  auto d7 = 0 <= qbpp::var_int("d7") <= 3 * 5 - 1;
  auto c3 = x - 3 * d3 == 2;
  auto c5 = x - 5 * d5 == 3;
  auto c7 = x - 7 * d7 == 5;
  auto f = x + 1000 * (c3 + c5 + c7);
  f.simplify_as_binary();

  auto solver = qbpp::easy_solver::EasySolver(f);
  solver.time_limit(1.0);
  auto sol = solver.search();

  std::cout << "x = " << sol(x) << std::endl;
  std::cout << sol(x) << " - 3 * " << sol(d3) << " = " << sol(*c3) << std::endl;
  std::cout << sol(x) << " - 5 * " << sol(d5) << " = " << sol(*c5) << std::endl;
  std::cout << sol(x) << " - 7 * " << sol(d7) << " = " << sol(*c7) << std::endl;
}

3つの制約は次のように表現される c3, c5、および c7。それぞれは、対応する等式が成り立つ場合に0となるQUBOペナルティ項に変換される。

次に、 x を、大きなペナルティ重み（1000）を用いて最小化します。これにより、制約条件を満たすことが、関数 f の値を小さくすることよりも優先されます。 x.

最後に、Easy Solverは時間制限（1.0秒）内でfの低エネルギー解を検索し、得られた値は以下のように出力される：

x = 68
- 3 * 22 = 2
- 5 * 13 = 3
- 7 * 9 = 5

したがって、

\[\begin{aligned} x &\equiv 68 & (\bmod 105) \end{aligned}\]

最小解は $x=68$ である。

最終更新日: 2025.12.31