Cogs 513. 八(容斥原理)

1. 八

   ★☆ 输入文件：eight.in 输出文件：eight.out 简单对比

   时间限制：1 s 内存限制：128 MB

   【问题描述】

   八是个很有趣的数字啊。八=发，八八=爸爸，88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样，有趣吧。当然题目和这些都没有关系。

   某个人很无聊，他想找出[a,b]中能被8整除却不能被其他一些数整除的数。

   【输入文件】

   第一行一个数n，代表不能被整除的数的个数。第二行n个数，中间用空格隔开。第三行两个数a，b，中间一个空格。

   【输出文件】

   一个整数，为[a,b]间能被8整除却不能被那n个数整除的数的个数。

   【样例输入】

   eight.in

   3

   7764 6082 462

   2166 53442

   【样例输出】

   eight.out

   6378

   【数据规模】

   对于30%的数据， 1≤n≤5，1≤a≤b≤100000。

   对于100%的数据，1≤n≤15，1≤a≤b≤10^9，N个数全都小于等于10^4大于等于1。

/*
一道容斥一眼题.
全集就是[l,r]中8的倍数的个数了.
考虑不合法的部分就是8的其他数的LCM了
n这么小 二进制拆分一下枚举子集就好了.
*/
#include<iostream>
#include<cstdio>
#define MAXN 20
#define LL long long
using namespace std;
LL n,a[MAXN],l,r,ans,tot,Lcm;
LL gcd(LL a,LL b)
{
    if(!b) return a;
    return gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
    return a*b/gcd(a,b);
}
void slove()
{
    ans=r/8-(l-1)/8;
    for(int s=1;s<=(1<<n)-1;s++)
    {
        tot=0;Lcm=8;
        for(int i=0;i<n;i++)
          if(s&(1<<i)) tot++,Lcm=lcm(Lcm,a[i]);
        if(tot&1) ans-=r/Lcm-(l-1)/Lcm;
        else ans+=r/Lcm-(l-1)/Lcm;
    }
}
int main()
{
    freopen("eight.in","r",stdin);
    freopen("eight.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    scanf("%d %d",&l,&r);
    slove();
    printf("%d",ans);
    return 0;
}