每日一题：至少被一个元素整除的数个数

题目

给定一个 $m$ 个元素的集合，问 $1-n$ 中有多少个数能被集合中至少一个元素整除。$(n <= 1e9, m <= 20)$

Solution

容斥原理，二进制枚举集合的所有子集，求子集的 $lcm$，如果子集大小是奇数，则 $res += n / lcm$，否则 $res-= n / lcm$。

Code

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL a[40];
int main() {
  LL N, M, ans = 0, gd;
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; i++) {
    scanf("%d", &a[i - 1]);
  }
  LL F = (1 << M) - 1;
  for (int i = 1; i <= F; i++) {
    LL cnt = 0;
    for (int j = 0; j < M; j++) {
      if (i & (1 << j)) {
        cnt++;
        if (cnt == 1)
          gd = a[j];
        else
          gd = gd * a[j] / (__gcd(a[j], gd));
      }
    }
    if (cnt & 1) {
      ans += N / gd;
    } else
      ans -= N / gd;
  }
  printf("%d\n", ans);
  return 0;
}