齿轮 - 题目列表

题意

给出 $n$ 个齿轮，第 $i$ 个齿轮的齿数是 $a_i$ 。
要从中选出恰好 $k$ 个齿轮组成一个齿轮组。

一个齿轮组的损耗因子定义为这 $k$ 个齿轮齿数的最大公约数。

要求对每个 $t \in [1, m]$ ，输出：

gcd 恰好等于 $t$ 的 $k$ 元组合个数

答案对 $10^9+7$ 取模。

思路

先看一个可以直接验证的小数据暴力：

cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int a[25];
int choose_idx[25];
int ans[1005];

void dfs(int pos, int last) {
    if (pos == k + 1) {
        int g = 0;
        for (int i = 1; i <= k; i++) {
            g = std::gcd(g, a[choose_idx[i]]);
        }
        ans[g]++;
        return;
    }

    for (int i = last + 1; i <= n; i++) {
        choose_idx[pos] = i;
        dfs(pos + 1, i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i <= m; i++) {
        ans[i] = 0;
    }

    dfs(1, 0);

    for (int i = 1; i <= m; i++) {
        cout << ans[i];
        if (i == m) {
            cout << '\n';
        }
        else {
            cout << ' ';
        }
    }

    return 0;
}

暴力版直接枚举所有大小为 $k$ 的组合，算出它们的 gcd，然后计数。
这当然只能跑很小的数据，但它把题意表达得很直接。

第一步：先数“gcd 是 $t$ 的倍数”的方案数

固定一个 $t$ 。
如果一个组合的 gcd 是 $t$ 的倍数，那么这个组合里的每个数都必须是 $t$ 的倍数。

设：

$cnt[t] = $ 数组里有多少个数能被 $t$ 整除

那么从这些数里任选 $k$ 个，就得到一个 gcd 为 $t$ 的倍数的组合。
所以：

$ways[t] = C(cnt[t], k)$

这里 $ways[t]$ 数的不是“gcd 恰好等于 $t$ ”，而是：

gcd 属于 $t, 2t, 3t, \ldots$ 这些倍数的所有组合

第二步：从大到小做容斥

设：

$ans[t] = $ gcd 恰好等于 $t$ 的组合数

那么：

$ways[t] = ans[t] + ans[2t] + ans[3t] + \ldots$

于是只要按 $t$ 从大到小枚举，就可以把更大的倍数答案先减掉：

$ans[t] = ways[t] - ans[2t] - ans[3t] - \ldots$

这就是这题的核心容斥。

组合数怎么求

因为需要大量计算 $C(x, k)$ ，而 $n \leqslant 10^6$ ，所以直接预处理：

$fact[i]$
$inv\_fact[i]$

然后用：

$C(n, k) = fact[n] \cdot inv\_fact[k] \cdot inv\_fact[n-k]$

在 $O(1)$ 时间求每个组合数。

代码

cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXM = 1000000 + 5;
const i64 MOD = 1000000007LL;

int n, m, k;
int a[MAXM];
int freq[MAXM];
int divisible_cnt[MAXM];
i64 fact[MAXM], inv_fact[MAXM];
i64 exact_ans[MAXM];

i64 quick_pow(i64 base, i64 exp) {
    i64 ans = 1 % MOD;
    base %= MOD;

    while (exp > 0) {
        if (exp & 1) {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }

    return ans;
}

void init_comb(int up) {
    fact[0] = 1;
    for (int i = 1; i <= up; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    inv_fact[up] = quick_pow(fact[up], MOD - 2);
    for (int i = up; i >= 1; i--) {
        inv_fact[i - 1] = inv_fact[i] * i % MOD;
    }
}

i64 C(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        freq[a[i]]++;
    }

    init_comb(n);

    for (int d = 1; d <= m; d++) {
        for (int x = d; x <= m; x += d) {
            divisible_cnt[d] += freq[x];
        }
    }

    // ways[d] = gcd 是 d 的倍数的方案数
    // exact[d] = gcd 恰好等于 d 的方案数
    for (int d = m; d >= 1; d--) {
        i64 ways = C(divisible_cnt[d], k);
        i64 sub = 0;
        for (int x = d + d; x <= m; x += d) {
            sub += exact_ans[x];
            if (sub >= MOD) {
                sub -= MOD;
            }
        }

        exact_ans[d] = (ways - sub) % MOD;
        if (exact_ans[d] < 0) {
            exact_ans[d] += MOD;
        }
    }

    for (int d = 1; d <= m; d++) {
        cout << exact_ans[d];
        if (d == m) {
            cout << '\n';
        }
        else {
            cout << ' ';
        }
    }

    return 0;
}

复杂度

设值域上界为 $m$ 。

统计 $cnt[t]$ ： $O(m \log m)$
从大到小做倍数容斥： $O(m \log m)$
预处理阶乘： $O(n)$

总时间复杂度：

$O(n + m \log m)$

空间复杂度：

$O(n + m)$

总结

这题的标准套路是：

先统计“所有数都能被 $t$ 整除”的组合数
再按倍数关系把“gcd 恰好等于 $t$ ”还原出来

所以本质上是一题：

倍数统计
组合数
容斥还原 exact gcd

的组合题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

子任务编号	$n\le$	$m\le$	$k\le$	分值
$1$	$10$	$10^6$	$10$	$10$
$2$	$10^3$	$10^3$	$10^3$	$20$
$3$	$10^6$	$10^3$	$2$	$5$
$4$	$10^6$	$10^6$	$1$	$5$
$5$	$10^6$	$10^6$	$2$	$20$
$6$	$10^6$	$10^6$	$10^6$	$40$

齿轮

目录

题意

思路

第一步：先数“gcd 是 ttt 的倍数”的方案数

第二步：从大到小做容斥

组合数怎么求

代码

复杂度

总结

一图流解析

第一步：先数“gcd 是 $t$ 的倍数”的方案数