3. 剰余演算

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

3.1. 剰余演算の基本的性質

次のような性質が成り立つ。

\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つ以上の場合は注意を要する。

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

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

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

\[(ax)\%p = 1\%p\]

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

フェルマーの小定理より

\[a^{p-1}\%p = aa^{p-2}\%p= 1\%p\]

であり、これから

\[a^{-1}\%p = a^{p-2}\%p\]

となる。すなわち

\[(a/b)\%p = \{(a\%p)\times (b^{p-2})\%p\}\%p\]

と、積に帰着できる。

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

• \(2^N\%(10^9+7)\) を求める例

#include <iostream>
const int MOD = 1000000007;

int main()
{
	long long N; std::cin >> N;
	int ans = 1;
	for(int i=0; i<N; i++)
	{
		ans *= 2;
		ans %= MOD;
	}
	std::cout << ans << std::endl;
	return 0;
}