已知序列 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;
}