https://vijos.org/p/1629

描述

八是個很有趣的數字啊。八=發，八八=爸爸，88=拜拜。當然最有趣的還是8用二進制表示是1000。怎么樣，有趣吧。當然題目和這些都沒有關系。

某個人很無聊，他想找出[a,b]中能被8整除卻不能被其他一些數整除的數。

格式

輸入格式

第一行一個數n，代表不能被整除的數的個數。

第二行n個數，中間用空格隔開。

第三行兩個數a，b，中間一個空格。

輸出格式

一個整數，為[a,b]間能被8整除卻不能被那n個數整除的數的個數。

樣例1

樣例輸入1

3 7764 6082 462 2166 53442 Copy

樣例輸出1

6378 Copy

限制

各個測試點1s

提示

對于30%的數據， 1≤n≤5，1≤a≤b≤100000。

對于100%的數據，1≤n≤15，1≤a≤b≤10^9，N個數全都小于等于10000大于等于1。

來源

Rcx 原創
NOIP 2009·Dream Team 模擬賽 第一期 第一題

?

二進制生成子集

1 #include <algorithm> 2 #include <iostream> 3 4 using namespace std; 5 6 #define LL long long 7 LL n,a,b,ans,cant[23]; 8 9 LL GCD(LL a,LL b) 10 { 11 if(a%b==0) return b; 12 return GCD(b,a%b); 13 } 14 LL LCM(LL a,LL b) 15 { 16 return a/GCD(a,b)*b; 17 } 18 19 int main() 20 { 21 cin>>n; 22 for(int i=1;i<=n;i++) cin>>cant[i]; 23 cin>>a>>b; a--; 24 ans=b/8-a/8; //(1<<n)-1 所有情況數 25 for(int i=1;i<=(1<<n)-1;i++) 26 { 27 LL lcm=8,cnt=0; //保證最小公倍數 一定有8這個 因子 28 for(int j=0;j<n;j++) 29 if(i&(1<<j)) //壓縮為2進制 從右開始 如果J==1 表示有第j個數 30 lcm=LCM(lcm,cant[j+1]),cnt++; 31 if(cnt&1) ans-=b/lcm-a/lcm; 32 else ans+=b/lcm-a/lcm; 33 } 34 cout<<ans; 35 return 0; 36 }

?

轉載于:https://www.cnblogs.com/Shy-key/p/7308729.html

總結

以上是生活随笔為你收集整理的Vijos——T 1629 八的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。