nefu 519 昨日重现

昨日重现

Problem : 519 Time Limit : 1000ms Memory Limit : 65536K

description

兴安黑熊在高中学习数学时，曾经知道这样一个公式：f(n)=1^2+2^2+3^2+.......+n^2,这个公式是可以化简的，化简后的结果是啥它却忘记了，也许刚上大二的你能记得。现在的问题是想要计算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

hint

本题4分，容易超时

我第一遍提交上去wa..

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    long long n,ans;
    while(cin>>n)
    {
           ans=(n*(n+)/)%;
           ans=((((ans*(*n+))/)%))%;
           cout<<ans<<endl;

    }
    return ;
}

公式应用错误，本想可以相乘除3再取余就不用判断哪一个会被3整除，但是这样的话公式不对了，样例虽然对上但是大数就不对了。。。。

所以便老实地按着老师讲的写，就ac了。。。

#include <iostream>
#include <math.h>
using namespace std;//1/6*n*(n+1)*(2n+1)

int main()
{
    long long n,ans,num;
    while(cin>>n)
    {
       ans=n*(n+);
       ans=ans/;
       if(ans%==)
       {
           ans=ans/;
           ans=ans%;
           num=(*n+)%;
           num=(ans*num)%;
       }
       else
       {
           num=(*n+)/;
           num=num%;
           ans=ans%;
           num=(ans*num)%;
       }
       cout<<num<<endl;
    }
    return ;
}

总结！！

(a+b)%c=(a%c+b%c)%c

(a*b)%c=((a%c)*(b%c))%c

 (a^b)%c=(a%c)^b;^代表幂

1^2+2^2+3^2+.......+n^2=n(n+1)(2n+1)/6

1^3+2^3+...+n^3=[n(n+1)/2]^2