当前位置：首页 > news >正文

咕咕嘎嘎!!!(hard)

news 2025/8/2 5:52:29

咕咕嘎嘎!!!(hard)

题目描述

企鹅喜欢收集石头，他有 $n$ 个编号不同的石头，编号分别为 $1$ 到 $n$。现在企鹅想从这 $n$ 个石头中选出 $m$ 个石头带回家。但是，企鹅认为如果选出的 $m$ 个石头的编号的最大公约数（$\gcd$）为 $1$，这些石头就会打架。为了防止石头打架，企鹅想知道有多少种选择石头的方案满足选出的 $m$ 个石头的编号的 $\gcd$ 不为 $1$。（假如选了 $3$ 个石头，分别是 $3$、$6$、$2$，那么 $\gcd(2,3,6)=1$。）由于方案数可能很大，请对 $10^9+7$ 取模。（easy 版本和 hard 版本仅数据范围不同。）

注：只选定一个石头，则最大公约数视为这个石头的编号本身。

输入描述:

第一行包含两个整数 $n$ 和 $m \left( 1 \leq m \leq n \leq 4 \times 10^7 \right)$ 。

输出描述:

输出一个整数，表示满足条件的方案数，对 $10^9+7$ 取模。

示例1

输入

5 2

输出

说明

只有选择 $(2, 4)$ 这一种方案

示例2

输入

6 3

输出

说明

只有选择 $(2, 4,6)$ 这一种方案

示例3

输入

85 25

输出

661928654

解题思路

赛时写了个 $O(n \log{n})$ 的做法一直 TLE，逆天数据范围和时限只允许 $O(n)$ 的算法过，甚至常数大一点还是会 TLE，很难不喷这出题人。但很奇怪的是赛时过了一堆人，而我却完全不知道有什么 $O(n)$ 的做法，果然赛后一问才知道是没学过的莫比乌斯反演。前几天学了一下莫比乌斯反演并尝试进行推导证明，参考博客 [POI 2007] ZAP-Queries，下文就不再对莫比乌斯反演进行详细介绍了。个人的理解是，莫比乌斯反演是对与因子相关的容斥原理的抽象表示，$F(n)$ 则对应着某些集合求交集后的大小。而 $f(n)$ 对应着某些集合求并集的大小。然后题目一般是求 $f(n)$，但不好表示出来，而 $F(n)$ 则容易表示出来。

先给出 $O(n \log{n})$ 的做法，参考 D. Counting Rhyme，就是求有多少个数对的 $\gcd$ 恰好为 $d$。不过本题要求的是有多少组大小为 $m$ 的数，其 $\gcd$ 恰好为 $d \left( 2 \leq d \leq n \right)$。定义 $f(d)$ 表示满足“$m$ 个数的 $\gcd$ 恰好为 $d$”的组数，可以通过容斥得到，即 $f(d) = C_{\left\lfloor n/d \right\rfloor}^{m} - \sum\limits_{i=2}^{\left\lfloor n/d \right\rfloor}{f(i \cdot d)}$，其中 $C_{\left\lfloor n/d \right\rfloor}^{m}$ 表示从 $1 \sim n$ 个数中选出 $m$ 个 $\gcd$ 是 $d$ 的倍数的数的方案数。

最后答案就是 $\sum\limits_{i=2}^{n}{f(d)}$，时间复杂度为 $O(n \log{n})$，无法通过。

再给出 $O(n)$ 的莫比乌斯反演的做法。要求满足 $m$ 个数的 $\gcd \ne 1$ 的组数，等价于用 $m$ 个数构成的所有组数 $C_{n}^{m}$ 减去满足 $m$ 个数的 $\gcd = 1$ 的组数。为此定义 $f(d)$ 表示满足 $m$ 个数的 $\gcd = d$ 的组数，由 $F(d) = \sum\limits_{d \mid i}{f(i)}$ 知道 $F(d)$ 表示满足 $m$ 个数的 $\gcd$ 为 $d$ 的倍数的组数，所以 $F(d) = C_{\left\lfloor n/d \right\rfloor}^{m}$。再由莫比乌斯反演得到 $f(d) = \sum\limits_{d \mid i}\mu(\tfrac{i}{d})F(i) = \sum\limits_{d \mid i}\mu(\tfrac{i}{d})C_{\left\lfloor n/i \right\rfloor}^{m}$。我们只需求 $f(1) = \sum\limits_{i=1}^{n}\mu(i)C_{\left\lfloor n/i \right\rfloor}^{m}$，按理来说直接枚举一遍 $O(n)$ 是可以过的，但本题就是要卡常恶心你，这部分必须要通过数论分块降到 $O(\sqrt{n})$ 才能过。

AC 代码如下，时间复杂度为 $O(n)$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 4e7 + 5, mod = 1e9 + 7;int prime[N], mu[N], cnt;
bool vis[N];
int fact[N], inv[N];void get_prime(int n) {mu[1] = 1;for (int i = 2; i <= n; i++) {if (!vis[i]) prime[cnt++] = i, mu[i] = -1;for (int j = 0; prime[j] * i <= n; j++) {vis[prime[j] * i] = true;if (i % prime[j] == 0) break;mu[prime[j] * i] = -mu[i];}}for (int i = 1; i <= n; i++) {mu[i] += mu[i - 1];}
}int C(int a, int b) {if (a < b) return 0;return 1ll * fact[a] * inv[b] % mod * inv[a - b] % mod;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;get_prime(n);fact[0] = inv[0] = inv[1] = 1;for (int i = 1; i <= n; i++) {fact[i] = 1ll * fact[i - 1] * i % mod;}for (int i = 2; i <= n; i++) {inv[i] = LL(mod - mod / i) * inv[mod % i] % mod;}for (int i = 2; i <= n; i++) {inv[i] = 1ll * inv[i] * inv[i - 1] % mod;}int ret = C(n, m);for (int i = 1; i <= n; i++) {int j = n / (n / i);ret = (ret - LL(mu[j] - mu[i - 1]) * C(n / i, m)) % mod;i = j;}ret = (ret + mod) % mod;cout << ret;return 0;
}

强行 $O(n)$ 计算也是可以的，但需要剪枝。实现需要单独处理 $m=1$ 的情况，直接输出 $n-1$ 即可。然后注意到对于组合数 $C_{\left\lfloor n/i \right\rfloor}^{m}$，只有 $\left\lfloor n/i \right\rfloor \geq m \Rightarrow i \leq \left\lfloor n/m \right\rfloor$ 才有意义，因此 $i$ 最大枚举到 $\left\lfloor n/m \right\rfloor$。

AC 代码如下，时间复杂度为 $O(n)$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 4e7 + 5, mod = 1e9 + 7;int prime[N], mu[N], cnt;
bool vis[N];
int fact[N], inv[N];void get_prime(int n) {mu[1] = 1;for (int i = 2; i <= n; i++) {if (!vis[i]) prime[cnt++] = i, mu[i] = -1;for (int j = 0; prime[j] * i <= n; j++) {vis[prime[j] * i] = true;if (i % prime[j] == 0) break;mu[prime[j] * i] = -mu[i];}}
}int C(int a, int b) {if (a < b) return 0;return 1ll * fact[a] * inv[b] % mod * inv[a - b] % mod;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;if (m == 1) {cout << n - 1;return 0;}get_prime(n);fact[0] = inv[0] = inv[1] = 1;for (int i = 1; i <= n; i++) {fact[i] = 1ll * fact[i - 1] * i % mod;}for (int i = 2; i <= n; i++) {inv[i] = LL(mod - mod / i) * inv[mod % i] % mod;}for (int i = 2; i <= n; i++) {inv[i] = 1ll * inv[i] * inv[i - 1] % mod;}int ret = C(n, m);for (int i = 1; i <= n / m; i++) {if (mu[i] == 1) ret = (ret - C(n / i, m)) % mod;else if (mu[i] == -1) ret = (ret + C(n / i, m)) % mod;}ret = (ret + mod) % mod;cout << ret;return 0;
}