.. highlight:: c++

===============
剰余演算
===============
競技プログラミングではしばしば剰余演算が必要となる。ここでその基本をまとめておく。

剰余演算の基本的性質
=====================
次のような性質が成り立つ。

.. math::
 :nowrap:

 \begin{eqnarray*}
 (a\%p)\%p &=& a\%p\\
 (ab)\%p &=& \{(a\%p)×(b\%p)\}\%p = \{(a\%p)×b\}\%p\\
 (a+b)\%p &=& \{(a\%p)+(b\%p)\}\%p = \{(a\%p)+b\}\%p
 \end{eqnarray*}
 
%p%p = %pと捉えて%pをくくり出しているようにみれば覚えやすいかもしれない。

積、和が3つ以上の場合は注意を要する。

.. math::
 :nowrap:

 \[
 (abc)\%p = \{(ab)\%p×(c\%p)\}\%p = \{(ab)\%p×c\}\%p = [\{(a\%p)×b\}\%p×c]\%p
 \]

aの剰余をとる :math:`\to` bを掛けて更に剰余をとる :math:`\to` cをかけて更に剰余をとる、の手順でok。4つ以上も同じ。

割り算についてはさらに注意が必要である。 :math:`(a/b)\%p = (ab^{-1})\%p` と書けるが、 :math:`b^{-1}` は通常の逆元ではない。逆元は

.. math::
  (ax)\%p = 1\%p

を満たすxがaの逆元として定義される。
逆元はフェルマーの小定理を用いて計算することが出来る。

フェルマーの小定理より

.. math::
 a^{p-1}\%p = aa^{p-2}\%p= 1\%p

であり、これから

.. math::
 a^{-1}\%p = a^{p-2}\%p

となる。すなわち

.. math::
 (a/b)\%p = \{(a\%p)\times (b^{p-2})\%p\}\%p

と、積に帰着できる。

例えば :math:`(143/13)\%7 = (143\times 13^5)\%7` となるわけである。 

* :math:`2^N\%(10^9+7)` を求める例

 .. literalinclude:: cpp/mod/main.cpp