Other answers already deal with
- useusing modular (long
long) integer arithmetic (rolfl) - speedspeeding up the inner loop by predicting the outcome of the if
if(Florian F)
A third possible speedup consists of grouping equal B\$B\$ values together. If the same value B[i]\$B_i\$ occurs k\$k\$ times, you can handle them all together with (k-1)+M/B instead of kM/B\$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 evenmakeeven make use of another general optimization (for hackkerrankHackerRank and similar competitions), — namely to make sure that my I/O is fast if the input iseven for large ..input.
Other answers already deal with
- use modular (long) integer arithmetic (rolfl)
- speed 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)+M/B instead of kM/B modular multiplications.
Using these three optimizations my worst test case took 0.19s - and I didn't evenmake use of another general optimization (for hackkerrank and similar competitions), namely to make sure that my I/O is fast if the input is large ...
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.
Other answers already deal with
- use modular (long) integer arithmetic (rolfl)
- speed 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)+M/B instead of kM/B modular multiplications.
Using these three optimizations my worst test case took 0.19s - and I didn't evenmake use of another general optimization (for hackkerrank and similar competitions), namely to make sure that my I/O is fast if the input is large ...