最大公約数 (GCD)
$P$ と $Q$ を二つの正の整数とする。 最大公約数（GCD）の計算は、QUBO問題として定式化できる。
$p$、$q$、$r$ を以下の制約を満たす正の整数とする：
\[\begin{aligned} p\cdot r &= P \\ q\cdot r &=Q \end{aligned}\]明らかに、$r$ は $P$ と $Q$ の公約数である。 したがって、これらの制約を満たす $r$ の最大値が $P$ と $Q$ の最大公約数となる。 このような $r$ を求めるため、HUBO定式化では $−r$ を目的関数として用いる。
QUBO++プログラム
上記の考えに基づき、以下のQUBO++プログラムは2つの整数の最大公約数を計算する。
P = 858 および Q = 693:
#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"
int main() {
const int P = 858;
const int Q = 693;
auto p = 1 <= qbpp::var_int("p") <= 1000;
auto q = 1 <= qbpp::var_int("q") <= 1000;
auto r = 1 <= qbpp::var_int("r") <= 1000;
auto constraint = (p * r == Q) + (q * r == P);
auto f = -r + constraint * 1000;
f.simplify_as_binary();
auto solver = qbpp::easy_solver::EasySolver(f);
solver.time_limit(1.0);
auto sol = solver.search();
std::cout << "GCD = " << sol(r) << std::endl;
std::cout << sol(p) << " * " << sol(r) << " = " << P << std::endl;
std::cout << sol(q) << " * " << sol(r) << " = " << Q << std::endl;
}
このプログラムでは、 p, q、および r は整数変数として定義され、その範囲は $[1,1000]$ です。
式制約は、両方の制約が満たされたときに 0 に評価されるように構築されています。
目的関数 -r は、ペナルティ係数 1000を乗じたペナルティ係数で乗算された制約項と組み合わされ、結果式は f.
EasySolverは、 fを最小化する解を検索する。
結果として得られる p, q、および r は以下の通り出力される：
GCD = 33
21 * 33 = 858
26 * 33 = 693
この出力は、858 と 693 の最大公約数が正しく 33 と得られたことを確認する。
最終更新日: 2026.01.11