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;
}