ACM-ICPC 2018 沈阳赛区网络预赛 G.Spare Tire (容斥)

题目链接：传送门

给你一个规律

给你一个n和一个m

求下标为1~n内所有与m互质的数的an的总和，答案mod1000000007

题解：

推出规律：

的前n项和为  

找出m的所有素因子 （素因子肯定不超过9个）

通过容斥定理找出1~n中与m不互质的数，例如m有一个素因子为2，那么2 4 6 8 10 12 14都不与m互质，那么我们可以提出一个2，总共有n/2个数，运用上面的式子进行求和，用了奇数个素因子要减去，偶数个素因子要加上，公式运用逆元。

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll inv2 = 500000004;//2的逆元 
ll inv6 = 166666668;//6的逆元 
const int MAXN = 10005;
int prime[MAXN+1];
void getPrime() {
	memset(prime, 0, sizeof(prime));
	for(int i = 2; i <= MAXN; i++){
		if(!prime[i]){
			prime[++prime[0]] = i;
		}
		for(int j = 1; j <= prime[0] && prime[j] <= MAXN/i; j++){
			prime[prime[j]*i]=1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
} 

ll cc(ll n, ll i){
	n = n / i;
    return ( n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod  *i%mod*i%mod
		+ n%mod*(n+1)%mod*inv2%mod  *i%mod )%mod;
}


int main() {
	ll n, m;
	getPrime();
	while(~scanf("%lld%lld",&n,&m)){
		vector<int> q;
		int ans = m;
		for(int i = 1; i <= prime[0]; i++){
			if(m%prime[i] == 0){
				q.push_back(prime[i]);
				while(ans%prime[i] == 0){
					ans /= prime[i];
				}
			}
		}
		if(ans != 1){
			q.push_back(ans);
		}
		ans = cc(n,1);
		ll ans2 = 0;
		int len = q.size();
		ll tmp;
		for(int i = 1; i < (1<<len); i++){
			int flag = __builtin_popcount(i);//有多少个1 代表有多少个质因子 
			tmp = 1;
			for(int j = 0; j < len; j++){
				if(i&(1<<j)){
					tmp *= q[j];	
				}
			}
			tmp = cc(n,tmp);
			if(flag%2){//奇数个质因子 
				ans2 = (ans2 % mod + tmp % mod) % mod;
			} else {//偶数个质因子 
				ans2 = (ans2 % mod - tmp % mod + mod) % mod;
			}
		}
		printf("%lld\n",(ans%mod-ans2%mod+mod)%mod);
	}
	return 0;
}