総和の剰余(mod) を計算したい
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; }
(+-*)の演算をする度に剰余を取ると思っておいて良さそう。除算は逆元が絡むのでまた別の話。