因为数据比较小，我的方法非常蠢。。
直接枚举M个数的集合的子集，记为s
然后球子集s里的数的最小公约数，并统计里面的数量，记为cnt
然后看小于n的数中，有多少个最小公约数的倍数，记为t
看cnt的奇偶性，奇数就加t，偶数就减t（容斥定理）
然后就做完了，因为数据小，对于这题复杂度足够了
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e2 + 5;LL n;
int S[MX], m;LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;
}LL lcm(LL a, LL b) {return a / gcd(a, b) * b;
}LL solve(LL x) {return (n - 1) / x;
}int main() {//freopen("input.txt", "r", stdin);while(~scanf("%I64d%d", &n, &m)) {int tot = 0, t;for(int i = 0; i < m; i++) {scanf("%d", &t);if(t) S[tot++] = t;}m = tot;LL ans = 0;for(int s = 1; s < (1 << m); s++) {int cnt = 0, sign = false;LL x = 1;for(int i = 0; i < m; i++) {if(s >> i & 1) {x = lcm(x, S[i]);if(x >= n) {sign = true;break;}cnt++;}}if(sign) continue;ans += solve(x) * (cnt % 2 ? 1 : -1);}printf("%I64d\n", ans);}return 0;
}