已知序列 Sₙ 由连续自然数的和构成，即 S₁=1，S₂=1+2，S₃=1+2+3，...，Sₙ=1+2+3+...+n 。

编写一个程序，计算并输出序列S₁~Sₙ的和除以1000000007的余数。

【输入描述】

输入一个正整数 n 。 1≤n≤10⁹

【输出描述】

输出序列Sₙ的总和除以1000000007的余数

【输入样例1】

3

【输出样例1】

10

【输入样例2】

10000

【输出样例2】

716668838

【输入样例3】

123456

【输出样例3】

334404958

【参考程序】80分解法

1 + ... + n ，可以用 for 循环加，每次求和对MOD取余；也可以用 n * (n + 1) / 2 ，注意强转成 long long 类型；然后再对 Sn 进行求和，每次求和对MOD取余。

// 爱码岛编程 
#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

// 1~n求和
long long sum(int n) {
    long long s = (long long)n * (n + 1) / 2;
    return s % MOD;
}

int main() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += sum(i);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

【参考程序】100分解法

当数据范围比较大的时候，上方程序时间复杂度比较大，所以可以用数学公式，求解。

n(n+1)(2n+1)/12  + n(n+1)/4

因为除法不能使用模运算性质，所以需要求出 12 和 4 的在求模意义下的乘法逆元。

// 爱码岛编程
#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

// 快速幂算法（取模）：a^b % MOD
long long pow_mod(long long a, long long b) {
    long long result = 1;
    a %= MOD;
    while (b) {
        if (b & 1)
            result = (result * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return result;
}

// 求a在模MOD下的乘法逆元（费马小定理 ）
long long inv(long long a) { 
    return pow_mod(a, MOD - 2); 
}

int main() {
    long long n;
    cin >> n;

    //( n(n+1)(2n+1)/6  + n(n+1)/2 ) / 2
    long long inv_12 = inv(12); // 12在模1e9+7下的乘法逆元
    long long inv_4 = inv(4);

    long long sum1 = ((n * (n + 1) % MOD * (2 * n + 1) % MOD) * inv_12) % MOD;
    long long sum2 = (n * (n + 1) % MOD * inv_4) % MOD;

    cout << (sum1 + sum2) % MOD << endl;

    return 0;
}

题解和视频讲解