被8整除（容斥原理）

admin

题目描述
八是个很有趣的数字啊。八=发，八八=爸爸，88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样，有趣吧。当然题目和这些都没有关系。 某个人很无聊，他想找出[a,b]中能被8整除却不能被其他一些数整除的数。

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

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

样例输入
3
7764 6082 462
2166 53442

样例输出
6378

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

admin

1. 
   
2. #include <cstdio>
   
3. #include <cstring>
   
4. #include <iostream>
   
5. using namespace std;
   
6. #define LL long long
   
7. int n, m[130], a, b;
   
8. LL ans;
   
9. LL gcd (LL a, LL b){//最大公因数
   
10.     if (! b)
    
11.         return a;
    
12.     return gcd (b, a % b);
    
13. }
    
14. LL lcm (LL a, LL b){//最小公倍数
    
15.     return a * b / gcd (a, b);
    
16. }
    
17. void dfs (int k, int Index, LL v){//k代表第几次并集，Index代表到了第几个集合，v代表这个集合，如v=8，就代表8的倍数这个集合
    
18.     if (v > b)//超出范围就没有意义
    
19.         return ;
    
20.     if (k % 2 == 0)//第偶数次加，第基数次减
    
21.         ans += b / v - a / v;
    
22.     else
    
23.         ans -= b / v - a / v;
    
24.     for (int i = Index + 1; i <= n; i ++){
    
25.         LL t = lcm (v, m[i]);//求着两个集合的并集
    
26.         dfs (k + 1, i, t);//递归求解
    
27.     }
    
28. }
    
29. int main (){
    
30.     scanf ("%d", &n);
    
31.     for (int i = 1; i <= n; i ++)
    
32.         scanf ("%d", &m[i]);
    
33.     scanf ("%d %d", &a, &b);
    
34.     dfs (0, 0, 8);//从第0次开始
    
35.     printf ("%lld\n", ans);
    
36.     return 0;
    
37. }

复制代码