hdu 4059 The Boss on Mars(容斥)

?

?

定义S = 1^4 + 2^4 + 3^4+.....+n^4，现在减去与n互质的数的4次方，问共减少了多少。

?

容斥原理，可以先把与n不互质的数的4次方求出来。那就先对n进行质因子分解，对质因子的组合运用容斥原理，质因子个数为奇数就加，偶数就减。其实与求[1,n]内与n互质的数的个数类似，该题重点是计算，防止乘法溢出。

?

对于求解1^4 + 2^4 + 3^4+.....+n^4，可以先类比1^2+2^2+...+n^2的求法，那么求4次方，

首先(n+1)^5= n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 5*n^1 + 1.

那么2^5 = (1+1)^5 = 1^5 + 5*1^4 + 10*1^3 + 10*1^2 + 5*1^1 + 1.

3^5 = (2+1)^5 = 2^5 + 5*2^4 + 10*2^3 + 10*2^2 + 5*2^1 + 1.

........

........

(n+1)^5 = n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 5*n^1 + 1.

将上述所有等式相加，两边抵消相同项，得到(n+1)^5 = 5*(1^4+2^4+……n^4)+10*(1^3+2^3+……+n^3)+10*(1^2+2^2+……+n^2)+5*(1+2+……+n)+n+1，

将1^3+2^3+……+n^3 = (n+1)^2*n^2/4和1^2+2^2+……+n^2 = (n*(n+1)*(2*n+1))/6带入上式，化简得到：

1^4+2^4+……n^4 = (n*(n+1)*(2n+1)*(3*n*n+3*n-1))/30。

因为要取余，要求30对1000000007的逆元，用扩展欧几里得即可。

?

?

#include 
  
   
#include 
   
     #include