【ZOJ-3233-Lucky Number】 容斥原理

ZOJ-3233-Lucky Number
题意就是给你一堆幸运数，在给你一堆不幸运数，要求一个区间内的数有多少个数满足至少是一个幸运数的倍数，而且不是每个不幸运数的倍数。
我们可以把这两个问题分开来看，首先我们可以利用容斥求出所有至少是一个幸运数的倍数的数的个数，我们只要在这个过程中给把满足第二种条件的保留就可以了，把第二种条件进一步表达，就变为了不能整除所有不幸运数的$lcm$，而如果我们当前枚举的$lcm$为$num$,所有不幸运数的$lcm=um$,我们怎样去掉这之中作为$um$的倍数的情况呢我们只要减去$n/(lcm(num,um))$即可，所以这道题就做完了，这道题坑点有lcm可能超过longlong,这种时候我们发现一定满足第二种条件，所以只要只计算第一种条件的数量即可。
（另外，ZOJRE可能会返回wa，因为这个-6 )=_=||
容斥原理第六题代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1005;
ll a[maxn];
ll b[maxn];
int n,m,i,en,flag;
ll LCM;
long long ans;
ll gcd_(ll a, ll b)
{return b ==0? a : gcd_(b, a % b);
}
ll lcm_(ll a, ll b)
{return a / gcd_(a, b) * b;
}void dfs(int pos,ll num,int p,ll x)
{if(p==0){long long tmp=x/num;if(flag==0) tmp=tmp-x/lcm_(num,LCM);if(i&1) ans+=tmp;else ans-=tmp;return ;}if(pos==en) return ;if(lcm_(num,a[pos])<=x) dfs(pos+1,lcm_(num,a[pos]),p-1,x);dfs(pos+1,num,p,x);return ;
}
int main()
{ll x,y;while(scanf("%d%d%lld%lld",&m,&n,&x,&y)!=EOF){flag=0;LCM=1;if(m==0&&n==0&&x==0&&y==0) break;ll ans1=0,ans2=0;for(int i=0;i<m;i++) scanf("%lld",&a[i]);for(int i=0;i<n;i++){scanf("%lld",&b[i]);LCM=lcm_(LCM,b[i]);}if(LCM<0)//爆longlong所以不需要统计第二种情况{flag=1;en=m;ans=0;for(i=1;i<=m;i++) dfs(0,1,i,y);ans1+=ans;ans=0;for(i=1;i<=m;i++) dfs(0,1,i,x-1);ans1-=ans;printf("%lld\n",ans1);}else{en=m;ans=0;for(i=1;i<=m;i++) dfs(0,1,i,y);ans1+=ans;ans=0;for(i=1;i<=m;i++) dfs(0,1,i,x-1);ans1-=ans;printf("%lld\n",ans1);}}return 0;
}