首页 > 代码库 > hdu--2576--高中数学..
hdu--2576--高中数学..
这题 绝逼是以前高中学到数列的时候做的难题...
就是忘记了 我一开始就直接开了个数组做 导致了mle 然后就觉得应该是去找数学公式了
这题的 数学推导过程很复杂的... 我直接写纸上了
设Tn = 1 + (1+2) + (1+2+3) + .....(1+2+3+...n)
所以
发现 效果很差啊...<不会拍照>
我还是直接手写吧...
接下去的重点就是 化简 1^2+2^2+3^2+....n^2
其实它就是等于 (1+2+3+....n)+(2+3+...n)+(3+....n)+....n 不难理解 就是将上面的平方全部拆开来 x^2 x为几 就会出现几次
然后这就可以运用 等差数列求和
化简为:[(n+1)n+(n+2)(n-1)+(n+3)(n-2)+....(n+n)(n-(n-1))]/2这边 不要直接写成(2n)*1 这样对下面的分解有很大影响
我在下面的式子都省略了/2因为写起来太不方便了 就在最后化简的时候出现 这边注明下
然后 我们把它给乘开来 即
(n^2+n-0)+(n^2+n-2)+(n^2+n-6)+....(n^2+n-(n-1)*n)--一共有n项
然后 仔细观察 会发现 0 = 0*1 2 = 1*2 6 = 2*3 12 = 3*4 ..... 最后一项:(n-1)*n
然后这n项中都有n^2和n 所以可以化简求得
x = n^3 + n^2 -(2+6+12+...+(n-1)*n) 至于后面的话 就可以化简为上2行提过的 我们先将它从式子中拿出来
z = 2+6+....+(n-1)*n= 1*2+2*3+....(n-1)*n=1*(1+1)+2*(2+1)+3*(3+1)+....(n-1)*(n-1+1) = 1^2+2^2+3^2+...(n-1)^2+(1+2+3+...n-1)
至于z中的1^2+2^2+3^2+...(n-1)^2就是Sn-1 因为我们将Sn看成1^2+2^2+3^2+...n^2
所以可以将x这个式子化简为 n^3+n^2-Sn-1-n(n-1)/2=Sn*2
即3Sn=n^3+n^2-n(n-1)/2这里还可以就是简单的化简下 我这边不写了
最终可以得到Sn=1^2+2^2+3^2+.....+n^2=n(n+1)(2n+1)/6
然后在将Sn+n(n+1)/2
最终得到了Tn = 1*2+2*3+3*4+(n-1)*n = n(n+1)(n+2)/3
因为这题的话 本来就预先/2所以最终 ans[n] = n(n+1)(n+2)/6
因为mod = 20090524; mod^2是在long long范围内 mod^3就超出了long lnog 的范围
所以 需要将它分布来乘
同时n(n+1)肯定能整除2 (n+1)(n+2)当然也满足肯定能整除2 习惯上 我们还是选择第一个
然后 要注意的是n(n+1)/2%(mod*3)这边要mod*3因为要保证得到的ans可以整除3 因为我们已经是先确定了n(n+1)(n+2)可以整除6
为什么*3就可以保证了呢?
x%(mod*y)=ans 那么ans = k*y 这样就解释了ans为什么可以整除y
1 #include <iostream> 2 using namespace std; 3 4 typedef long long LL; 5 const LL mod = 20090524; 6 7 int main() 8 { 9 int t;10 LL n , ans;11 cin >> t;12 while( t-- )13 {14 cin >> n;15 ans = n*(n+1)/2%(mod*3);16 ans = ans*(n+2)/3%mod;17 cout << ans << endl;18 }19 return 0;20 }
hdu--2576--高中数学..