HDU The Boss on Mars（容斥原理）

题目大意：

ACM 有 n 名员工，现在是他们从老板那里拿薪水的时候了。所有员工都从 1 到 n 编号。原因不明，如果员工的工作编号是 k，他今年可以获得 k^4 Mars 美元。所以为 ACM 工作的员工非常富有。

因为员工人数太多，ACM 的老板必须分配太多的钱，他想明年解雇工作号与 n 共质的人。现在老板想知道解雇后他会节省多少钱。

思路：先求出1~n的每个数的四次方的求和，然后再减去n的因子的四次方的求和。把n的因子的质因子找出来，然后使用容斥原理（我容斥原理用的方法是二进制）去做。

求和公式： ( 搜来的 )

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int vis[10005],prime[10005];
int ksm(int x,int y){int ans=1;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;
}
int fun(int x){//求 a ^ 4 的前 x 项和return (x*(x+1)%mod*(2*x+1)%mod*(3*x*x%mod+3*x%mod-1+mod)%mod)%mod*ksm(30,mod-2)%mod;
}
signed main(){int cnt=0;for(int i=2;i<=10000;i++){//埃式筛求 1 ~ 10000 之间的素数 if(vis[i]) continue;prime[cnt++]=i;for(int j=i*2;j<=10000;j+=i){vis[j]=1;}}int _;cin >> _;while(_--){int n;cin >> n;vector<int> v;//存质因数 int m=n;for(int i=0;i<cnt;i++){//挑选 n 的质因子 if(m%prime[i]==0){v.push_back(prime[i]);while(m%prime[i]==0) m/=prime[i];}}if(m>1) v.push_back(m);//若不为 1 ，说明还留下 1 个质因子 int ans=fun(n),res=0;for(int i=1;i<(1<<v.size());i++){int num=1,sum=0;//num 代表几种不同质因子组成的最小因子 ，sum 代表质因子的个数 for(int j=0;j<v.size();j++){ if((i>>j)&1) sum++,num*=v[j];}int tmp=num*num%mod*num%mod*num%mod*fun(n/num);//求出 num 的倍数(不大于 n ) 的四次方之和。将这个最小因子的四次方之和提出，剩下的就是 a^4 的前几项和//例如：2^4 + 4^4 + 6^4 + 8^4 = 2^4 * ( 1^4 + 2^4 + 3^4 + 4^4 )if(sum%2) res=(res+tmp)%mod;//容斥原理 else res=(res-tmp)%mod;}ans=((ans-res)%mod+mod)%mod;cout << ans << endl;}return 0;
}