Other answers already deal with
- using modular (
long) integer arithmetic (rolfl) - speeding up the inner loop by predicting the outcome of the
if(Florian F)
A third possible speedup consists of grouping equal \$B\$ values together. If the same value \$B_i\$ occurs \$k\$ times, you can handle them all together with \$k - 1 + \frac{M}{B}\$ modular multiplications instead of \$\frac{kM}{B}\$.
Using these three optimizations my worst test case took 0.19s, and I didn't even make use of another general optimization (for HackerRank and similar competitions) — namely to make sure that my I/O is fast even for large input.
Hagen von Eitzen
- 121
- 4
default