Properties Of Modulo
I am just starting with competitive programing and usually numbers get way too large so we tend to work with $$ \mod 10^9+7$$
I am familiar with some properties of modulo like,
$$(a+b) \mod c = (a\mod c+b\mod c) \mod c$$$$(a-b) \mod c = (a\mod c-b\mod c) \mod c$$$$(a*b) \mod c = (a\mod c*b\mod c) \mod c$$
But recently I stumbled upon this formula,
$$y=\frac{4a^3-a^2}{3}$$
This is the Faulhaber Formula for $\sum_{i=0}^{n}{i^5}$, where $a=\sum_{i=0}^{n}{i}$.
Now this is what has me stuck.
In my scenario $a\approx10^{16}$ and the largest value I can store is $\approx 10^{19}$.
and I want to evaluate,
$$\frac{4a^3-a^2}{3} \mod 10^9+7$$
Clearly I cannot calculate $a^3$ due to overflow also I am finding it hard to distribute the modulo because of the $3$ in the denominator. How do I get around this?
Any suggestions will be helpful. Thanks.
$\endgroup$ 13 Answers
$\begingroup$We can use
$$a^3 \pmod{p} \equiv \color{red}[\color{blue}[(a \pmod{p}) \cdot (a \pmod{p})\pmod{p}\color{blue}] \cdot (a \pmod{p}) \color{red}]\pmod{p}$$
That is we keep computing modulo after each step of computation, hence the number stays within the limit of your computation.
$\endgroup$ 2 $\begingroup$You can take mod while multiplying numbers. After taking modulo separately to $a^3$ and $a^2$, you can still get the correct answer. Below is a piece of C++ code that show how you can take mod of $a^2$, $a^3$, etc.
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int main(){ long long a = /*something from the input*/; a %= mod; long long a2 = a; a2 *= a; a2 %= mod; //^ There we got the value of a^2 mod (1e9 + 7). long long a3 = a2; a3 *= a; a3 %= mod; //^ We got the value of a^3 mod (1e9 + 7) similarly. //TODO: implementation
}You then substitute the values of $a^2$ and $a^3$ into your formula. If you encounter greater powers later, just use the big mod algorithm:
long long big_mod(long long base, long long power, long long mod){ if (power == 0) return 1; else if (power == 1) return base%mod; else{ if (power%2 == 1) return (base * big_mod(base, power-1, mod))%mod; else return (big_mod(base, power/2, mod) * big_mod(base, power/2, mod))%mod; }
}The algorithm above runs in $\mathcal{O}(\log(\operatorname{power}))$ time.
$\endgroup$ $\begingroup$Hint $\bmod 10^{\large 9}\!+7\!:\,\ 10^{\large 9}\equiv -7\,\Rightarrow\ 10^{\large 10}\equiv -70,\,\ldots, 10^{\large 18}\equiv (-7)^{\large 2}\equiv 49,\,\ldots$
and $\ \bmod\, \color{#c00}2\!+\!3n\!:\,\ \dfrac{1}3\,\equiv\, \dfrac{1+ 2\!+\!3n} 3\,\equiv\, 1\!+\!n\ \ $ [here $\bmod 3\!:\ 10^{\large 9}\!+7\equiv 1^{\large 9}\!+1\equiv \color{#c00}2\:\!$]
$\endgroup$
