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