题意：
找到能被集合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; 
}