题解 SP6285 NGM2 - Another Game With Numbers

SP6285 NGM2 - Another Game With Numbers

简要题意

给定一个长为 $K$ 的数组 $a$，其中 $1 \le K \le 15$ 且 $a_i \le 100$，再给定一个数 $N$，其中 $1 \le N \le 10^9$，要求求出 $[1, N]$ 中有多少数不能被 $a$ 中任意一个数整除。

策略分析

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

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

参考代码

#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();
}