mod 上での基本的な演算(加算、減算、乗算)

mod 演算の初歩。

mod 上での加算

足した結果に mod をかける。それだけ。

code:cpp

int ans = (a + b) % mod;

code:py

ans = (a + b) % mod

ただし、特に型付き言語において、

足す$ 2項そのものが著しく大きい場合など、int型を超えた演算結果になる場合は、long longを使うか、先に$ 2項それぞれに mod をかけるとよい。

mod 上での減算

ここからはめんどくさいので、$ a - b, a \times bについて$ a, bいずれも mod 未満の値であるとする。

$ a - bをシンプルに計算すると、答えが負になる可能性がある。そこで、

$ a - b \equiv c \bmod Pならば、$ a - b + P \equiv c \bmod Pとしてもよいので、演算結果に$ Pを足して正の値に出来る。

code:cpp

int ans = (a - b + mod) % mod;

code:py

ans = (a - b + mod) % mod

mod 上での乗算

$ P = 10^9+7や$ 998244353というのは、

$ a, b < Pが保証されているとき、乗算しても$ 64bit 整数の範囲に収まるという性質上使われている値である。(特に後者はNTT-Friendly)

よって、$ 64bit 整数を使っているという前提の上で、乗算して mod をかけるだけでよい。

code:cpp

// a, b も long long である必要があるので注意。

long long ans = (a * b) % mod;

code:py

ans = (a * b) % mod