yn2011's blog

技術メモ

総和の剰余(mod) を計算したい

AtCoder

C - Sum of product of pairs で躓いたのでメモ。

総和の剰余(mod)

整数 a1, a2, a3 ... の 総和の剰余(mod) を計算したい。

(a1 + a2 + a3 ... ) % m

このとき、上の計算は以下と同値である。

(a1 % m + a2 % m + a3 % m ... ) % m

これを剰余演算の分配法則と同一性から示す。

剰余演算の分配法則から以下が成り立つ。

(a1 + a2) % m = (a1 % m + a2 % m) % m

すると、以下のように変形できる。

(a1 + a2 + a3 ... ) % m
= (a1 % m + (a2 + a3 ... )　% m ) % m
= (a1 % m + (a2 % m + (a3 + a4...) % m) % m) % m
...
= (a1 % m + a2 %m + ...) % m % m ...

また、剰余演算の同一性から以下が成り立つ。

a % m = (a % m) % m

したがって、

 (a1 % m + a2 %m + ...) % m % m ...
= (a1 % m + a2 %m + ...) % m

と変形できる。

なので、総和の剰余を求める場合は、剰余の総和を取って最後に剰余を取ってもいいし

int sum = 0;
for(int i = 0; i < n; i++) {
  sum += a[i] % m;
}
sum %= m;

変形前の式から見ると、加算する度に剰余を取ってもいい（オーバーフローを防げるので安全）

int sum = 0;
for(int i = 0; i < n; i++) {
  sum += a[i] % m;
  sum %= m;
}

(+-*)の演算をする度に剰余を取ると思っておいて良さそう。除算は逆元が絡むのでまた別の話。

参考