Properties Of Modulo

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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\:\!$]