给定一个整数 nn 和 mm 个不同的质数 p1,p2,…,pmp1,p2,…,pm。
请你求出 1∼n1∼n 中能被 p1,p2,…,pmp1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数 nn 和 mm。
第二行包含 mm 个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

1≤m≤161≤m≤16,
1≤n,pi≤1091≤n,pi≤109

输入样例：

10 2 2 3

输出样例：

7

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. typedef long long LL;
  9. const int N = 20;
  11. int p[N];
  12. int n,m;
  14. int main() {
  15.     cin >> n >> m;
  16.     for (int i = 0; i < m; ++i) cin >> p[i];
  18.     int res = 0;
  19.     for (int i = 1; i < 1 << m; ++i) {  //有m个数，有2^m - 1个选法（除了全不选）
  20.         int t = 1, cnt = 0;             //t表示质数乘积，cnt表示有多少个集合
  21.         for (int j = 0; j < m; ++j) {
  22.             if (i >> j & 1) {       //说明选了这个集合
  23.                 cnt++;
  24.                 if ((LL)t * p[j] > n) {
  25.                     t = -1;
  26.                     break;
  27.                 }
  28.                 t *= p[j];
  29.             }
  30.         }
  31.         if (t != -1) {
  32.             //奇数个集合就加上      n / t 表示有多少个n 整除t 的个数
  33.             if (cnt % 2) res += n / t;
  34.             else res -= n / t;
  35.         }
  36.     }
  37.     cout << res << endl;
  38.     return 0;
  39. }