昨日重现

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
 
05-07 09:36