1369. A Dot Product Under a Modulus
Two arrays a and b of n values are given, every entry already in the
range 0 to m-1. Print
(a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1]) mod m
as a value in 0 to m-1.
## What most people try first
Add up all n products into a 64-bit accumulator, then reduce once. Problem
1367 showed that reducing after every multiplication is necessary, so a reader
who has seen it often concludes that one reduction at the end of a SUM is
harmless. It is not, and the reason is arithmetic rather than algebra.
each product < m^2 = 10^18
n products < n * m^2 = 10^5 * 10^18 = 10^23
A signed 64-bit integer stops near 9.22 * 10^18. So the sum overflows even
though each individual product fits, and it does so silently: the wrapped value
is still a plausible looking number and % on it returns a plausible looking
residue.
## Reduce twice, once per operation
acc = 0
for i in 0 .. n-1:
acc = (acc + a[i] * b[i]) mod m
Now the largest value in flight is acc + a[i]*b[i], with acc below m and
the product below m^2. That is under 10^18 + 10^9, comfortably inside 64
bits.
## Why it is correct
Reduction commutes with both operations used here, so replacing the exact
running total by its residue at every step changes it only by multiples of m,
which cannot change the final answer. The invariant is that acc always equals
the exact partial sum modulo m, and it holds after each iteration because it
held before.
## The boundary that breaks a careless implementation
acc must start at 0, not at 1 % m. The empty sum is zero, and copying the
initialisation from the product version of this problem is the single most
common way to get every answer wrong by one factor.
## Overflow
The 64-bit bound above is the whole reason the constraints cap n at 10^5
and m at 10^9. In JavaScript a plain Number is exact only below 2^53,
about 9 * 10^15, so a product near 10^18 is rounded. The reference uses
BigInt.
## Cost
O(n) multiplications and O(n) reductions.
Constraints - `1 ≤ n ≤ 100000` - `2 ≤ m ≤ 1000000000` - `0 ≤ a[i] < m` - `0 ≤ b[i] < m`
Input
The first line contains two integers n and m.
The second line contains n integers, the array a.
The third line contains n integers, the array b.
Output
Print one integer, the dot product of a and b reduced modulo m, in the range 0 to m-1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.