题目链接:nefu 519 昨日重现

题目描述:

昨日重现
Time Limit:1000ms
Memory Limit:65536K
Description
兴安黑熊在高中学习数学时,曾经知道这样一个公式:f(n)=1² + 2² + 3² +.......+ n²,这个公式是可以化简的,
化简后的结果是啥它却忘记了,也许刚上大二的你能记得。现在的问题是想要计算f(n)对1007取余的值,你能帮帮他吗?
Input
输入数据有多组,每组一个数n. (1<=n <=1,000,000,000).
Output
输出f(n)对1007取余的值。
Sample Input
3
4
100
Sample Output
14
30
1005

思路:

数学公式有 ( 1² + 2² + 3² +.......+ n² ) mod 1007 = [ n * ( n + 1 ) * ( 2 * n + 1) / 6 ] mod 1007
由于会爆long long,可以用快速乘取模,然后把除以6转化成乘以6对1007的逆元inv(6,1007),即ans=n(n+1)*(2n+1)*inv(6,1007)。

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,n,p=1007;
ll inv(ll a,ll p)//求a对p的逆元inv(a,p)
{return a==1?1:(p-p/a)*inv(p%a,p)%p;}
ll quick_multiple(ll a,ll b)//快速乘,类似快速幂,要把快速幂中的乘法改成加法
{
    ll s=0;//不是s=1;
    while(b)
    {
        if(b&1)s=(s+a)%p;
        a=(a+a)%p;
        b=b/2;
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        ans=quick_multiple(n,n+1);
        ans=quick_multiple(ans,2*n+1);
        ans=(ans%p)*(inv(6,1007)%p)%p;
        printf("%lld\n",ans);
    }
    return 0;
}