Sum of numbers from 0 to 10^18 with modulus 10^9+7

Question

How to find sum of numbers from 0 to n modulus 10⁹ + 7, where n ≤ 10¹⁸?

I want to store the result in long long int only and not in array or string. My code results in a run time error.

const unsigned int m = 1000000007;

long long int n;
cin >> n;
long long int s = 0;
for (long long int i = 0; i < n; i++) {
    s = ((s % m) + (i % m)) % m;
}
cout << s << endl;

Answer 1

Sum of n natural numbers is given by the formula, n * (n + 1) / 2. So, you don't need to iterate over n to calculate the sum.

As, n can be up-to 10¹⁸, computing the sum using, (n * (n + 1) / 2) % MOD would result in integer overflow. Instead, modular arithmetic property, (a * b) % MOD is congruent to ((a % MOD) * (b % MOD)) % MOD, should be used to compute the sum. .

Thus, the sum can be computed using: ((n % MOD * (n + 1) % MOD) % MOD) / 2

The code would look something like this,

const long long int MOD = 1e9 + 7;
long long int n;

cin >> n;

long long s
s = ((n % MOD * (n + 1) % MOD) % MOD) / 2;

cout << s << '\n';