1367. Multiply Them Up Under a Modulus
Multiply n values together and print the product reduced modulo m. Every
value is already given in the range 0 to m-1.
n = 4, m = 1000000007 values 2 3 4 5 product 120 -> 120
n = 2, m = 999999937 values 999999936 999999936 -> 1
The second line is worth pausing on. 999999936 is m - 1, which is -1
modulo m, and -1 squared is 1. So the answer is 1 even though the exact
product is about 10^18.
## What most people try first
Multiply everything into one accumulator and reduce at the end. The exact
product of 200000 values near 10^9 has roughly 1.8 million digits. No fixed
width integer holds it, so this is not a matter of choosing a wider type.
## Reduce after every multiplication
acc = 1 mod m
for each value v:
acc = (acc * v) mod m
## Why it is correct
Reduction commutes with multiplication the same way it does with addition:
(x * y) mod m equals ((x mod m) * (y mod m)) mod m. Each step therefore
changes the accumulator only by a multiple of m, and because a multiple of
m is itself 0 modulo m, it can never alter the final residue. The accumulator starts at the empty product, 1.
Since m is at least 2 here, 1 mod m is simply 1, but the reduction is
written anyway so the shape matches problem 1372, where m may be 1 and the
distinction becomes real.
## Overflow, which is the real content here
acc is below m and v is below m, so the product acc * v is below
m^2. With m as large as 10^9 that is 10^18.
- A signed 32-bit integer stops at 2147483647, so it is hopeless.
- A signed 64-bit integer holds up to about
9.22 * 10^18, so10^18is safe - with room to spare. This is why the modulus is capped at
10^9and not - higher: at
m = 4 * 10^9the product would reach1.6 * 10^19and 64 bits - would fail too.
- In JavaScript a plain
Numberis exact only up to2^53, about -
9 * 10^15. A product near10^18is silently rounded, which produces a - wrong answer with no error at all. The reference uses
BigInt.
## Cost
O(n) multiplications, with one modulus each.
Constraints - `1 ≤ n ≤ 200000` - `2 ≤ m ≤ 1000000000` - `0 ≤ each value < m`
Input
The first line contains two integers n and m.
The second line contains n integers, each already in the range 0 to m-1.
Output
Print one integer, the product of the values 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.