从 0 到 10^18 的数字总和，模数为 10^9+7

Question

如何求 0 到 n 模数 10⁹ + 7 的数之和，其中 n ≤ 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 来计算总和。

因为，n 可以是 up-to 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';