読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Garnerのアルゴリズム

この記事ではGarnerのアルゴリズムについて説明する。
参考にしたのはこのpdf。
http://www.csee.umbc.edu/~lomonaco/s08/441/handouts/Garner-Alg-Example.pdf

概要

{x=a_1\;(\mathrm{mod}\; m_1)}
{\cdots}
{x=a_n\;(\mathrm{mod}\; m_n)}
という形の連立方程式の最小解を求めるアルゴリズム。ただし{m_1,\ldots,m_n}はどの対も互いに素であるとする。計算量は{O(n^2)}

具体的には最小解を
{x=v_1+v_2m_1+v_3m_1m_2+v_4m_1m_2m_3+\cdots+v_nm_1m_2\cdots m_{n-1} }
と置いて、{ v_1,\ldots,v_n} を求める操作を行う。

アルゴリズムの流れ

まず{\mathrm{mod}\;m_1}で考えると{v_1=a_1}であることが分かる。

次に{v_1,\ldots,v_i}まで求まっていたとすると、{\mathrm{mod}\;m_{i+1}}で考えれば
{ x=v_1+v_2m_1+\cdots+v_{i+1}m_1m_2\cdots m_i = a_{i+1} }
である。左辺の{v_{i+1}}以外の項を移項して
{ v_{i+1}m_1m_2\cdots m_i=a_{i+1}-(v_1+v_2m_1+\cdots+v_{i}m_1m_2\cdots m_{i-1}) }
よって{m_1m_2\cdots m_i}の逆元を両辺にかければ{v_{i+1}}を得ることができる。

繰り返しこの作業を行えばすべての{v_i}を求めることができる。

具体例

連立方程式
{x=2\;(\mathrm{mod}\; 3)}
{x=1\;(\mathrm{mod}\; 5)}
{x=5\;(\mathrm{mod}\; 7)}
をGarnerのアルゴリズムで解いてみる。

まず解を{x=a+3b+15c}と置く。

{\mathrm{mod}\; 3}で考えると
{a=2}

{\mathrm{mod}\; 5}で考えると
{x=a+3b=1}
{3b=4}
{b=3}

{\mathrm{mod}\; 7}で考えると
{x=a+3b+15c=5}
{15c=1}
{c=1}

よって{x=a+3b+15c=2+3\cdot 3+15\cdot 1=26}が最小解。

最小性の証明

解を求めるプロセスを見れば分かるように、{v_i \le m_i-1 } が成り立っている。つまり
{ x \le (m_1-1)+m_1(m_2-1)+m_1m_2(m_3-1)+\cdots + m_1m_2\cdots (m_n-1) }
である。右辺は色々消えて
{ x \le m_1m_2\cdots m_n - 1 }
になる。中国剰余定理と合わせて考えれば解は最小であることがわかる。

応用

{(v_1+\cdots+v_nm_1m_2\cdots m_{n-1})\;\mathrm{mod}\;m_1m_2\cdots m_n}で最小解を求めてるのではなく、{v_1+\cdots+v_nm_1m_2\cdots m_{n-1}}が直接最小解になっている。そのため最小解のmod Pでの値を多倍長なしで求められる。これはyukicoderでも出題されている利用方法。

計算結果は10^18で収まるけど計算過程で巨大な数になる場合も使える。10^9程度の2種類のmodで計算した値をGarnerで復元すればいい。

コメント

Garnerのアルゴリズムについては冒頭のpdf以外に何も読んでないので何か間違ったこと言ってるかも。