次方数前缀和公式推导
之前训练赛上碰到了这么一道题：Problem - E - Codeforces
要求 \(\sum_{i=1}^n i^5\ (n~is~so~big)\)??，一般只会记平方数，立方数前缀和公式。这俩我都经常记不住
好在之前学过如果通过低次的次方数前缀和推到高次，但写这题的时候忘了，又滚去百度了一波。
为了加深记忆，写个博客记录下到底是怎么推的。
已知 \(\sum_{i=1}^n i=\dfrac {n*(n+1)}2\)??，求 \(\sum_{i=1}^n i^2\)??：
\[\sum_{i=1}^n (i+1)^3=\sum_{i=1}^n (i^3+3i^2+3i+1)\\ (n+1)^3-1=3\sum_{i=1}^n i^2+3\sum_{i=1}^n i^2+n\\ \sum_{i=1}^n i^2=\frac {(n+1)^3-n-1}{3}-\frac{n(n+1)}{2}=\frac {n(n+1)(n+2)}{6} \]同理，要求立方数的前缀和公式，则对 \(\sum_{i=1}^n (i+1)^4\)?? 进行同样的操作，同时我们也可从中得出一个结论：\(n\) 次方数的前缀和公式一定是个 \(n+1\) 次多项式。
这样推在高次的时候会挺麻烦的，可能要在草稿纸上算挺久化简化一年，但确实简单易懂，好想好记。
而且如果时间复杂度允许的话，也不用特意花大量时间去计算式子并化简、然后套公式 \(O(1)\)?? 求解；只需在草稿纸上根据二项式定理多展开几项，然后写好对应的函数 calx(n) 计算\(\sum_{i=1}^n i^x\)??，类似递归地调用一下即可，时间复杂度也是常数级的。
比如要求 \(i^7\)????????????????? 次方，那我们把 \(i^{4+1}\sim i^{7+1}\)????????????????? 都展开一下，然后 ??cal7(n) 调用 cal6(n) 调用 cal5(n)。。。一直到 cal3(n)（一般立方数的前缀和我们知道）递归结束假递归，每个函数都不一样。
感觉可能还有更好的方法来求解次方数前缀和问题？但私以为这个就够用了，于是就懒得去找了，总之先放这儿，以后如果学到了啥更优秀的方法再回头更新一波估计是莫得了。
顺便贴一下该题的代码，二分 + Java 处理大数。训练时写的，贼丑，慎看
import java.math.BigInteger;
import java.util.Scanner;
class Main {
static BigInteger cal(BigInteger x){
BigInteger x2=x.multiply(x);
BigInteger x1=x.add(BigInteger.ONE);
x1=x1.multiply(x1);
BigInteger ret=x2.multiply(x1);
// System.out.println(ret);
x=x.multiply(BigInteger.valueOf(2));
x2=x2.add(x2);
ret=ret.multiply(x.add(x2).subtract(BigInteger.ONE));
ret=ret.divide(BigInteger.valueOf(12));
return ret;
}
public static void main(String[] args) {
String P=new String();
String Q=new String();
Scanner in =new Scanner(System.in);
P=in.next();
Q=in.next();
BigInteger p=new BigInteger(P);
BigInteger q=new BigInteger(Q);
// System.out.println(p.divide(q));
BigInteger x=BigInteger.ZERO;
BigInteger ans=BigInteger.ZERO;
BigInteger d=BigInteger.ONE;
for(long i=1;;i++){
BigInteger ti=BigInteger.valueOf(i).pow(5);
BigInteger tx=ti.multiply(q);
if(tx.compareTo(p)>=0){
d=BigInteger.valueOf(i);
ans=tx;
break;
}
x=x.add(tx);
x=x.subtract(p);
// x=x.add(tx);
// x=x.subtract(p);
// if(x.multiply(BigInteger.valueOf(-1)).compareTo(p)>=0||tx.compareTo(p)>=0){
// d=BigInteger.valueOf(i);
// ans=tx;
// break;
// }
}
// System.out.println("x = "+x);
// System.out.println("d = "+ d);
x=p.subtract(x);
System.out.println(x);
// System.out.println(d);
// System.out.println(cal(d));
BigInteger dt=cal(d);
BigInteger mb=new BigInteger("1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
mb=mb.subtract(ans);
BigInteger l=d.add(BigInteger.ONE);
BigInteger r=new BigInteger("100000000000000000000");
BigInteger y=l;
while(l.compareTo(r)<=0){
BigInteger mid=l.add(r).divide(BigInteger.valueOf(2));
// System.out.println("mid = "+mid);
BigInteger t=cal(mid).subtract(dt);
t=t.multiply(q);
BigInteger cj=mid.subtract(d);
t=t.subtract(cj.multiply(p));
if(t.compareTo(mb)>=0){
y=mid;
r=mid.subtract(BigInteger.ONE);
}
else {
l=mid.add(BigInteger.ONE);
}
}
System.out.println(y);
}
}