容斥原理，居然没想到……要补一下数论了
原题：
小x最近对数字8很感兴趣，有8进制，2008奥运会之类的。
现在小x想知道，在[x,y]区间里，有多少个数能被8整除。
小y觉得题目太简单，于是给出n个其他数，问在[x,y]区间里，有多少个数能被8整除且不能被这n个数整除。
1≤n≤15，1≤x≤y≤10^9，N个数全都小于等于10^4大于等于1。
x-y区间这个问题，可以搞前缀和，求1-(x-1)和1-y，然后减
枚举2^n种 n个因子是否使用 的情况，然后搞8和 当前情况使用因子 的lcm，用x-1或y除这个lcm，得到在这个范围内能被lcm整除的有几个，如果用了奇数个，答案就减，偶数个就加
搞lcm的时候，如果lcm已经大于x-1或y，就不用再往下搞
代码；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int gcd(int x,int y){return (y)?gcd(y,x%y):x;}
int n,a[],xx,yy;
bool use[];
int ansx,ansy,bowl=;
void dfs(int x,int y){
if(x>n){
long long lcm=; int ge=;
for(int i=;i<=n;i++)if(use[i]){
lcm*=a[i]/gcd(lcm,a[i]);
if(lcm>y) break;
ge++;
}
if(ge%) bowl-=y/lcm;
else bowl+=y/lcm;
return ;
}
use[x]=false; dfs(x+,y);
use[x]=true; dfs(x+,y);
}
int main(){//freopen("ddd.in","r",stdin);
memset(use,,sizeof(use));
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
cin>>xx>>yy;
dfs(,yy); ansy=bowl;
bowl=;
dfs(,xx-); ansx=bowl;
cout<<ansy-ansx<<endl;
return ;
}