题意：给定n, a1,，a2，...，am，求小于n的整数中，至少能被一个ai整除的数有多少个。数据范围：n<=2^31，m<=10，每个ai<=20
由容斥原理，ans=Σ|ai|-Σ|ai∩aj|+Σ|ai∩aj∩ak|-...+(-1)^(m-1)|a1∩a2∩...∩am|，这儿的交意思就是取最小公倍数。注意m<=10，考虑状态压缩。最小公倍数有性质[a,b,c]=[[a,b],c]，这使得多个数的最小公倍数可以依次计算。如果当前的二进制j为1，更新lcm=(lcm*a[j])/gcd(lcm,a[j]))。如果二进制中1的个数为奇数，则ans+=(n/lcm)，否则ans-=(n/lcm)。注意几个点：一是输入的ai可能为0，这种情况的ai直接去掉；二是要开long long，算答案的时候有可能会爆int。然后多组数据又被坑了一波......
1 #include<iostream> 2 #define ll long long 3 using namespace std; 4 5 int a[20]; 6 ll n,m,i,j; 7 8 ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} 9 10 int main(){ 11 while (cin>>n>>m){ 12 n--;int cnt=0; 13 for (i=0;i<m;i++) { 14 int x;cin>>x; 15 if (x!=0) a[cnt++]=x; 16 } 17 ll ans=0; 18 for (i=1;i<=(1<<cnt)-1;i++){ 19 int t=0;ll lcm=1; 20 for (j=0;j<cnt;j++) 21 if ((i>>j)&1){ 22 t++; 23 lcm=(lcm*a[j])/(gcd(lcm,a[j])); 24 } 25 if (t%2==1) ans+=(n/lcm);else ans-=(n/lcm); 26 } 27 cout<<ans<<endl; 28 } 29 return 0; 30 }