来源：牛客网
文章目录
题目描述题解：代码：
时间限制：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
;
ll x1
=x
;
y
=x1
-(a
/b
)*y1
;
x
=y1
;
return gcd
;
}
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;
}
