八是个很有趣的数字啊。八=发，八八=爸爸，88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样，有趣吧。当然题目和这些都没有关系。某个人很无聊，他想找出[a,b]中能被8整除却不能被其他一些数整除的数。
输入
第一行一个数n，代表不能被整除的数的个数。第二行n个数，中间用空格隔开。第三行两个数a，b，中间一个空格。a<=b<=1000000000
输出
一个整数，为[a,b]间能被8整除却不能被那n个数整除的数的个数。
样例输入
377646082462216653442
样例输出
6378
提示
对于30%的数据，1≤n≤5，1≤a≤b≤100000。对于100%的数据，1≤n≤15，1≤a≤b≤10^9，N个数全都小于等于10000大于等于1。
思路
一看就能想到是容斥原理，首先，怎么算区间[a,b]中p的倍数的个数呢？首先，算出区间[1,b]的p倍数的个数很简单：即可，为高斯取整，即下取整。所以，要算[a,b]中p的倍数的个数，直接用[1,b]中p倍数的个数减去[1,a)中p的倍数即可。即：b/p-(a-1)/p，注意，这里不能算[1,a]，因为a有可能也是p的倍数，如果算[1,a]就算不到a了。
然后就要解决容斥的问题了，设U为区间[a,b]中所有的整数，E为U中所有8的倍数，Ai为U中所有num[i]倍数（num[i]为题目给出的第i个不想被整除的数）发现，我们要求的就是：。如果你看不懂∩和∪，请看这张图：假设圆c1和c2分别代表集合C1，C2，则：C1∩C2=蓝色围起来的部分C1∪C2=红色围起来的部分
好了，这样的话就不难明白了（你可以自己画一个图看看）。
最后还有一个很重要的地方，同时能被num[1],num[2],…,num[N]整除的数不一定是num[1]·num[2]·…·num[N]的倍数，应该是lcm(num[1],num[2],…,num[N])的倍数。
代码
怎么实现呢？容斥原理嘛，加加减减，如果不明白容斥原理就自己百度吧，反正我是用dfs实现的，我不明白怎么用循环弄，因为你的循环次数都是不确定的，要乘的num[i]也是不确定的。所以就用dfs了，如果你一意想要用循环，百度吧……
#include<cstdio>#include<iostream>usingnamespacestd;#defineLLlonglong#defineMAXN20LLN,a,b,ans;LLnum[MAXN];LLgcd(LLa,LLb){return!b?a:gcd(b,a%b);}LLlcm(LLa,LLb){returna*b/gcd(a,b);}//求最小公倍数voiddfs(LLx,LLp,LLt){if(t>b)return;//如果你算出来的t比上界b还大，[a,b]中就肯定没有t的倍数了if(x%2==0)ans+=b/t-a/t;elseans-=b/t-a/t;//根据奇偶加减for(inti=p+1;i<=N;i++)//防止重复，从p+1开始dfs(x+1,i,lcm(t,num[i]));//注意一定是lcm(t,num[i])，我就因为写的t*num[i]而直接尴尬}intmain(){cin>>N;//longlong的格式控制符windows和linux系统评测不一样，索性就直接cin，cout了for(inti=1;i<=N;i++)cin>>num[i];cin>>a>>b;a--;//算的是[0,a)，所以提前a--dfs(0,0,8);//8肯定是全部要算上的，所以t从8开始cout<<ans;}
