华师一附中OI组

标题: 被8整除（容斥原理） [打印本页]
作者: admin    时间: 2020-2-2 08:14
标题: 被8整除（容斥原理）
题目描述
八是个很有趣的数字啊。八=发，八八=爸爸，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    时间: 2020-2-2 08:16

  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2