Сумма чисел от 0 до 10 ^ 18 с модулем 10 ^ 9 + 7

Question

Как найти сумму чисел от 0 до n по модулю 10 ⁹ + 7, где n & le; 10 ¹⁸

Я хочу сохранить результат только в long long int, а не в массиве или строке. Мой код приводит к ошибке во время выполнения.

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

Сумма n натуральных чисел задается формулой n * (n + 1) / 2.Таким образом, вам не нужно перебирать n , чтобы вычислить сумму.

As, n может быть до 10 ¹⁸ , вычисление суммы с использованием (n * (n + 1) / 2) % MOD приведет к переполнению целого числа.Вместо этого для вычисления суммы следует использовать модульное арифметическое свойство (a * b) % MOD, совпадающее с ((a % MOD) * (b % MOD)) % MOD.,

Таким образом, сумма может быть вычислена с использованием: ((n % MOD * (n + 1) % MOD) % MOD) / 2

Код будет выглядеть примерно так:

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';