算法基础之能被整除的数

能被整除的数

• 核心思想： 容斥原理

  • 总面积 = 1-2+3-4….

  • 总集合元素中个数 = 1-2+3-4….

  • 

  •   #include<iostream>
      #include<cstring>
      #include<algorithm>
      
      using namespace std;
      const int N = 20;
      typedef long long LL;
      
      int p[N];
      
      int main()
      {
          int n,m;
          cin>>n>>m;
          
          for(int i=0;i<m;i++) cin>>p[i];  //输入质数
          
          int res = 0;
          for(int i=1;i< 1 << m ;i++)  //用二进制数表示一张图 遍历所有取法
          {
              int t = 1 , cnt = 0;  //t为所有质数乘积 cnt为集合个数
              for(int j =0;j<m;j++)  //遍历图中每一位数
              {
                  if(i >> j & 1)  //若取到j集合
                  {
                      if((LL)t * p[j] > n)  //该取法失效
                      {
                          t = -1;
                          break;
                      }
                      t *= p[j];  //t为所有质数乘积
                      cnt++;  //集合个数++
                  }
              }
              if(t != -1)  //取法有效
              {
                  // n/t 为 该集合个数(不能整除 向下取整)
                  if(cnt % 2) res += n/t;  //集合个数为奇数 +
                  else res -= n/t;  //集合个数为偶数 -
              }
          }
          
          cout<<res;
      }