时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
定义S(n) = 12 + 22 + … + n2，输出S(n) % 1000000007。
注意：1 < n < 1e18。
输入描述:
多组输入，输入直到遇到EOF为止；
第一行输入一个正整数n。
输出描述:
输出S(n) % 1000000007的结果。
示例1
输入
1
2
1000
输出
1
5
333833500
题解：
平方和公式：12+22+32+…+n2=n(n+1)(2n+1)/6
（建议补一补高中的一些公式，我也没想起来 ）
注意题目是要mod的
模运算：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a b % p = ((a % p)b) % p
我们可以发现唯独没有除法的模运算，但是公式中有个 /6 需要处理，那我们可以用逆元的方式将除法变成乘法
逆元：整数a,b，满足a * b = 1（mod m），那么称b是a的模m乘法逆元
比如：A/B%C我们可以写成A * （1 / B）% C，这样就是AX%C的形式，如何求X？和上面的逆元结合起来就OK了
这样/6%mod，我就可以写成 inv（6）%mod
求逆元的方法这里就不详细介绍了
代码：
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{
if(b==0)
{
x=1;
y=0;
return a; //到达递归边界开始向上一层返回
}
ll gcd=exgcd(b,a%b,x,y);
ll y1=y; //把x y变成上一层的
ll x1=x;
y=x1-(a/b)*y1;
x=y1;
return gcd; //得到a b的最大公因数
}
ll inv(ll a,ll mod){
ll x,y;
ll gcd=exgcd(a,mod,x,y);
if(gcd!=1)return -1;
else return (x+mod)%mod;
}
int main()
{
ll n;
while(cin>>n){
ll ans=0;
ans=(((n%mod)*((n+1)%mod)%mod*((2*n+1)%mod))%mod);
ll inv6=inv(6,mod);
ans=(ans%mod*inv6%mod)%mod;
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号