链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
定义S(n) = 12 + 22 + … + n2,输出S(n) % 1000000007。
注意:1 < n < 1e18。
#include<bits/stdc++.h> using namespace std; #define p 1000000007 typedef long long ll; ll inv(ll a,ll b){ ll ans=1; a=a%p; while(b) { if(b&1) ans=(ans*a)%p; a=(a*a)%p; b>>=1; } return ans; } int main(){ ll n; while(scanf("%lld",&n)!=EOF) { n%=p; ll t=inv(6,p-2); ll s=n%p*(n+1)%p*(2*n+1)%p*t%p; printf("%lld\n",s%p); } return 0; }
知识点:乘法逆元,快速幂,模运算