題目描述

---

小x最近對(duì)數(shù)字8很感興趣，有8進(jìn)制，2008奧運(yùn)會(huì)之類的。
現(xiàn)在小x想知道，在[x,y]區(qū)間里，有多少個(gè)數(shù)能被8整除。
小y覺得題目太簡單，于是給出n個(gè)其他數(shù)，問在[x,y]區(qū)間里，有多少個(gè)數(shù)能被8整除且不能被這n個(gè)數(shù)整除

---

分析

啊啊啊啊啊，一道很水的容斥原理啦QWQ，枚舉出這個(gè)n個(gè)數(shù)所有和8的lcm的情況，奇減偶加，這道題最麻煩的地方在于枚舉出所有的情況，看那些超級(jí)大佬都是dfs枚舉情況，蒟蒻的我實(shí)在太菜（lan）了，就用二進(jìn)制枚舉情況咯！！！

//By Bibi /// .-~~~~~~~~~-._ _.-~~~~~~~~~-. /// __.' ~. .~ `.__ /// .'// \./ \\`. /// .'// | \\`. /// .'// .-~"""""""~~~~-._ | _,-~~~~"""""""~-. \\`. /// .'//.-" `-. | .-' "-.\\`. /// .'//______.============-.. \ | / ..-============.______\\`. /// .'______________________________\|/______________________________`. #include<bits/stdc++.h> #define rep(i,a,b) for(long long i=a;i<=b;++i) #define dep(i,a,b) for(long long i=a;i>=b;--i) using namespace std; const long long MAXN=20; typedef long long ll; ll read(){ll sum=0,flag=1;char c;for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=-1;for(;c>='0'&&c<='9';c=getchar())sum=(sum<<1)+(sum<<3)+c-'0';return sum*flag; } ll n; ll a[MAXN]; ll ans1,ans2; ll x,y; ll gcd(ll a,ll b){return b? gcd(b,a%b):a; } void init(){n=read();rep(i,0,n-1) a[i]=read();x=read();y=read(); } void work1(){rep(i,0,(1<<n)-1){ll tot=0,true_num=8;rep(j,0,n-1){if(i&(1<<j)){true_num*=a[j]/gcd(true_num,a[j]);if(true_num>x-1) break;tot++;}}if(tot&1) ans1-=(x-1)/true_num;else ans1+=(x-1)/true_num;} } void work2(){rep(i,0,(1<<n)-1){ll tot=0,true_num=8;rep(j,0,n-1){if(i&(1<<j)){true_num*=a[j]/gcd(true_num,a[j]);if(true_num>y) break;tot++;}}if(tot&1) ans2-=(y)/true_num;else ans2+=(y)/true_num;} } int main(){init();work1();work2();printf("%lld\n",ans2-ans1);return 0; }

總結(jié)

以上是生活随笔為你收集整理的8的倍数——题解（容斥原理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。