昨日重现 |
|||
|
|||
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 |
|||
sample_output |
|||
14 |
|||
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