文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1796

十年前的题了。。。。
题意：就是给一个m个数（可能不互质），问在小于n以内有多少个数与给的这n个数互质
我一看这个，很常规的二进制来容斥，心里想的是10分钟搞定，结果被坑了。。。
①：这道题有0，第一发RE了。。。
②：给的数不是互质的，哇让我长见识了，平时我们做的题都是互质的来容斥，然后我就想把公共的因子提出来，结果还是WA了，因为会有1的影响，比如1 3两个数的时候公共因子就是1，但是1 3 9的时候，要提个3出来。。。。又不考虑1了，结果。。。是要用所有数的<mark>lcm</mark>来容斥，哇，学到了。。。。

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
LL a[maxn];
LL LCM(LL a,LL b)
{
	return a/__gcd(a,b)*b;
}
int main()
{
	LL N,M;
	while(cin>>N>>M)
	{
		for(int i=0;i<M;i++)
		{
			cin>>a[i];
			if(a[i]==0)i--,M--;
		}
		N--;
		for(int i=0;i<=M/2;i++)swap(a[i],a[M-i-1]);
		LL ans=0;
		for(int sta=1;sta<(1<<M);sta++)
		{
			int cnt=__builtin_popcount(sta);
			LL n=1;
			for(int j=0;j<M;j++)if(sta&(1<<j))n=LCM(n,a[j]);//用lcm来容斥 
			if(cnt%2)ans+=N/n;
			else ans-=N/n;
		}
		cout<<ans<<endl;
	}
}