当前位置：首页 > news >正文

序列求和牛客网

news 来源：原创 2025/7/19 18:58:57

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

题目描述

定义S(n) = 12 + 22 + … + n2，输出S(n) % 1000000007。

注意：1 < n < 1e18。

输入描述:

多组输入，输入直到遇到EOF为止；第一行输入一个正整数n。

输出描述:

输出S(n) % 1000000007的结果。

输入

1
2
1000

输出

1
5
333833500

解题思路

为了求解 S(n)=12+22+…+n2 并对其取模 1000000007，我们可以利用数学公式来直接计算，而不是通过迭代累加，因为题目给定的 n 的范围非常大（1<n<1018），直接迭代会导致效率极低。

数学上，平方和公式为：

S(n)=12+22+…+n2=6n(n+1)(2n+1)

使用这个公式，我们可以快速计算出 S(n)，然后对其取模 1000000007。

错误代码示例

#include <iostream>using namespace std;const int MOD = 1000000007;// 快速乘法，防止整数溢出
long long mul_mod(long long a, long long b, long long mod) {long long res = 0;a = a % mod;while (b > 0) {if (b % 2 == 1) {res = (res + a) % mod;}a = (a * 2) % mod;b = b / 2;}return res;
}int main() {long long n;while (cin >> n) {// 使用公式计算 S(n)long long numerator = mul_mod(n, mul_mod(n + 1, (2 * n + 1), MOD), MOD);long long S_n = numerator * modInverse(6, MOD) % MOD; // 这里需要6的模逆元cout << S_n << endl;}return 0;
}// 求a在mod下的逆元，使用费马小定理
long long modInverse(long long a, long long mod) {return pow(a, mod - 2, mod);
}// 快速幂算法，计算 base^exp % mod
long long pow(long long base, long long exp, long long mod) {long long result = 1;while (exp > 0) {if (exp % 2 == 1) {result = (result * base) % mod;}base = (base * base) % mod;exp = exp / 2;}return result;
}

上面的代码中使用了一个 modInverse 函数来计算模逆元，这是因为在计算 S(n) 时，我们需要除以6，但在模运算中，我们通常通过乘以6的模逆元来实现除法。这里使用了费马小定理来计算逆元，它要求模数 MOD 是一个质数，而 1000000007 确实是一个质数。

然而，上面的代码在直接运行时会有一个问题：pow 函数在计算大幂次时可能会因为递归深度过大而导致栈溢出。由于 n 可以达到 1018，我们需要一个更稳健的快速幂实现，最好是基于迭代的。上面的 pow 函数已经是一个迭代版本，所以这部分是安全的，但我们要确保整个流程不会因为其他原因（如输入处理不当）而崩溃。

另外，上面的 mul_mod 函数实际上是一个二进制方法实现的快速乘法，用于防止在计算过程中出现整数溢出。在这个特定问题中，由于我们使用了模逆元和快速幂，整数溢出的风险被大大降低了，但保留这个函数仍然是一个好习惯。

最终，由于题目要求处理多组输入直到EOF，我们只需要在 main 函数中使用一个循环来不断读取输入并计算结果即可。上面的代码已经包含了这部分逻辑。

fast_mul 用于快速乘法，fast_pow 用于快速幂，以及 mod_inverse 用于计算模逆元。这些函数都设计为避免整数溢出，并且能够在处理大数时保持效率。主函数 main 使用这些函数来计算并输出 S(n) 的模值。

代码实现

#include <iostream>using namespace std;const int MOD = 1000000007;// 快速乘法，防止整数溢出（使用二进制方法）
long long fast_mul(long long a, long long b, long long mod) {long long res = 0;a %= mod;while (b > 0) {if (b & 1) { // 如果b的最低位是1res = (res + a) % mod;}a = (a << 1) % mod; // a乘以2（左移一位）b >>= 1; // b除以2（右移一位）}return res;
}// 快速幂算法（迭代版本），计算 base^exp % mod
long long fast_pow(long long base, long long exp, long long mod) {long long result = 1;base %= mod;while (exp > 0) {if (exp & 1) { // 如果exp的最低位是1result = fast_mul(result, base, mod);}base = fast_mul(base, base, mod); // base平方exp >>= 1; // exp除以2}return result;
}// 求a在mod下的逆元（使用费马小定理）
long long mod_inverse(long long a, long long mod) {return fast_pow(a, mod - 2, mod);
}int main() {long long n;while (cin >> n) {// 使用公式计算 S(n) = n * (n + 1) * (2n + 1) / 6 % MODlong long numerator = fast_mul(fast_mul(n, n + 1, MOD), (2 * n + 1), MOD);long long S_n = numerator * mod_inverse(6, MOD) % MOD;cout << S_n << endl;}return 0;
}