题意： 找到能被集合A中至少一个数整除，且集合B至少有一个不整除它
思路：容斥原理，其实等于A-AB=(a1+a2…an)+(a1B+a2B+…anB),容斥即可，果然dfs版的容斥是要快很多的，随便加个剪枝就250ms，大概比二进制快了10倍，以后容斥只用dfs写
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; int j,n1,n2; ll a[20],low,high,ans; ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;} ll lcm(ll a,ll b) { if((double)a/gcd(a,b)*b>high)return high+1; return a/gcd(a,b)*b; } void dfs(int pos,ll sum,int cnt,ll num,bool flag) { sum=lcm(sum,a[pos]); if(sum>num)return; if(flag){ if(cnt&1){ ans+=(num/sum); } else ans-=(num/sum); } else{ if(cnt&1)ans-=(num/sum); else ans+=(num/sum); } for(int i=pos+1;i<=n1;++i) dfs(i,sum,cnt+1,num,flag); } int main() { while(~scanf("%d%d%lld%lld",&n1,&n2,&low,&high)) { if(n1==0&&n2==0&&low==0&&high==0)break; ans=0; ll LCM=1; for(int i=1;i<=n1;++i) scanf("%lld",&a[i]); ll b; for(int j=1;j<=n2;++j) { scanf("%lld",&b); LCM=lcm(LCM,b); } for(int i=1;i<=n1;++i) dfs(i,a[i],1,high,1); for(int i=1;i<=n1;++i) dfs(i,a[i],1,low-1,0); for(int i=1;i<=n1;++i) a[i]=lcm(a[i],LCM); for(int i=1;i<=n1;++i) dfs(i,a[i],1,high,0); for(int i=1;i<=n1;++i) dfs(i,a[i],1,low-1,1); printf("%lld\n",ans); } return 0; }