G30 容斥原理 集合的并

G30 容斥原理 集合的并（内网）

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 20;
LL n, m, prim[N];

LL calc()// 容斥原理
{
  LL res = 0;
  for (LL i = 1; i < 1 << m; i++)// 枚举状态
  { 
    LL t = 1, sign = -1;
    for (LL j = 0; j < m; j++) // 过滤状态
      if (i & 1 << j)
      {
        if (t * prim[j] > n)
        {
          t = 0;
          break;
        }
        t *= prim[j]; // 质数的积
        sign = -sign;
      }
    if (t) res += n / t * sign; // 交集的和
  }
  return res;
}
int main()
{
  cin >> n >> m;
  for (LL i = 0; i < m; i++) cin >> prim[i];
  cout << calc();
  return 0;
}