SP6285 NGM2 - Another Game With Numbers

简要题意

给定一个长为 的数组 ，其中 且 ，再给定一个数 ，其中 ，要求求出 中有多少数不能被 中任意一个数整除。

策略分析

显然满足我们要求的数不能被 整除，同时也不能被 中任意 个元素的最小公倍数整除。所以最朴素的想法是通过筛选出能够被整除的数的个数，再用 减去它。如果你想到这里了，那么恭喜你这道题已经做完了。由于本题的 非常非常小，所以我们可以直接暴力枚举出 个数的所有组合的最大公约数， 求出 中能整除一个数 的数有多少，然后做容斥就能得出答案了。

具体来讲，我们可以用状态压缩来对所有组合进行枚举，即对于 ，我们从 枚举到 ，枚举到的第 个数的第 位为 则表示本次选取这位，否则不选，然后每次对所有选取的位置上的数求最小公倍数 ，然后用 除以 就能得出 中能整除 的数的个数 。根据容斥原理，如果当前选取了奇数个数，就要把 加入到答案中，否则将答案减去 。注意这样算出的结果是 中能整除 中某个数的数的个数，所以最后要用 减去它才能得到答案。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

namespace SHAWN {
    const int N = 107;
    LL a[N];
    LL n, k, ans;
    inline LL gcd(LL x, LL y) { return !y ? x : gcd(y, x % y); }
    inline LL lcm(LL x, LL y) { return x * y / gcd(x, y); }
    signed work()
    {
        cin >> n >> k;
        for (int i = 1; i <= k; ++i) { cin >> a[i]; }
        for (int i = 1; i < (1 << k); ++i) {
            LL lrc = 1, cnt = 0;
            for (int j = 1; j <= k; ++j) {
                if (i & (1 << (j - 1))) {
                    lrc = lcm(lrc, a[j]);
                    ++cnt;
                }
            }
            if (cnt & 1) { ans += n / lrc; }
            else { ans -= n / lrc; }
        }
        ans = n - ans;
        cout << ans << '\n';
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}