# 剰余問題
:::{container} prog-cpp
以下の問題はHi-QUBOを用いて解くことができます.
次の条件を満たす最小の非負整数 $x$ を求めます:
- $x$ を3で割った余りが2
- $x$ を5で割った余りが3
- $x$ を7で割った余りが5
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}
$$
## Hi-QUBO プログラム
以下のプログラムは,この剰余問題の解 $x$ を求めます:
```{literalinclude} /../programFiles/cppPrograms/example/math/modular-arithmetic-program1.cpp
:language: cpp
:caption: modular-arithmetic-program1.cpp
```
3つの制約は `c3`,`c5`,`c7` として表現されています.
それぞれは,対応する等式が成り立つときに0になるQUBOペナルティ項に変換されます.
次に,制約の充足を $x$ の削減よりも優先するために,大きなペナルティ重み（1000）を用いて `x` を最小化します.
最後に,Easy Solverが制限時間（1.0秒）内で f の低エネルギー解を探索し,得られた値は以下のように出力されます:
```{include} /../programFiles/markDown/example/math/modular-arithmetic.md
:start-after:
:end-before:
```
したがって,
$$
\begin{aligned}
x &\equiv 68 & (\bmod 105)
\end{aligned}
$$
最小の解は $x=68$ です.
:::
:::{container} prog-python
以下の問題は PyQBPP を使って解くことができます.
次の条件を満たす最小の非負整数 $x$ を求めます:
- $x$ を 3 で割った余りが 2,
- $x$ を 5 で割った余りが 3,
- $x$ を 7 で割った余りが 5.
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}
$$
## PyQBPP プログラム
以下のプログラムは,この余り問題の解 $x$ を求めます:
```{literalinclude} /../programFiles/pythonPrograms/example/math/modular-arithmetic-program1.py
:language: python
:caption: modular-arithmetic-program1.py
```
3つの制約は `c3`,`c5`,`c7` として表現されています.
それぞれは,対応する等式が成り立つときに 0 となる QUBO ペナルティ項に変換されます.
大きなペナルティ重み（1000）を使って `x` を最小化することで,`x` の削減よりも制約の充足が優先されます.
最後に,Easy Solver がキーワード引数で指定された制限時間（1.0秒）内で f の低エネルギー解を探索し,得られた値は以下のように出力されます:
```{include} /../programFiles/markDown/example/math/modular-arithmetic.md
:start-after:
:end-before:
```
したがって,
$$
\begin{aligned}
x &\equiv 68 & (\bmod 105)
\end{aligned}
$$
最小の解は $x=68$ です.
:::