[USACO08DEC] Patting Heads S

题意

第 $i$ 头牛抽到数字 $A_i$ 。它会拍所有满足 $A_j\mid A_i$ 的其它牛 $j$ ，求每头牛要拍多少头牛。

数据范围为 $N\leqslant 10^5$ 、 $A_i\leqslant 10^6$ ，数字可以重复。

思路

朴素枚举

直接枚举有序牛对 $(i,j)$ ，检查 $i\neq j$ 且 $A_i$ 能否被 $A_j$ 整除：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 11:59
 * update_at: 2026-07-19 11:59
 */
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据朴素解，直接检查每一对牛是否满足整除关系。

const int MAXN = 105;

int n;
int value[MAXN];

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> value[i];

    for (int i = 1; i <= n; i++) {
        int answer = 0;
        for (int j = 1; j <= n; j++) {
            if (i != j && value[i] % value[j] == 0) answer++;
        }
        cout << answer << '\n';
    }
    return 0;
}

这种写法完全对应题意，适合作为小数据参考答案，但需要 $O(N^2)$ 次整除判断，无法处理 $N=10^5$ 。

相同数值只计算一次

两头数值同为 $x$ 的牛，能够拍到的牛数完全相同。先建立频率表：

frequency[d]=\#\{j\mid A_j=d\}.

对于某个数值 $x$ ，能整除它的每个 $d$ 都贡献 frequency[d] 头牛，所以包含自己的暂时计数为：

divisor\_count[x]=\sum_{d\mid x}frequency[d].

可以为每个 $x$ 单独枚举约数，但还要处理平方根、配对约数与重复值。更统一的方向是反过来问：一个除数 $d$ 会贡献给哪些 $x$ ？答案正是：

d,2d,3d,\ldots

因此枚举每个实际出现的 $d$ ，把 frequency[d] 加到所有倍数的 divisor_count 中即可。

为什么最后只减一

divisor_count[A_i] 统计所有满足 $A_j\mid A_i$ 的牛，其中一定包含当前牛 $i$ ，因为任何正整数都整除自身。题目要求拍“其它牛”，所以答案要减去当前牛这一头。

如果还有其它牛与 $i$ 的数值相同，它们也满足整除关系，应该保留在答案中。因此无论 frequency[A_i] 是多少，都只减 1，不能减去整个频次。

以样例中数值为 2 的牛为例，能整除 2 的牛的数值是 1,2,2，暂时计数为 3。减去当前牛自己后，仍可拍数值为 1 的牛和另一头数值为 2 的牛，答案为 2。

原 main.py 也采用倍数贡献，但最坏分布下要在 Python 解释器中执行上千万次内层累加，因此没有通过评测。C++ 使用大小约为 $10^6$ 的连续全局数组，倍数循环的常数明显更小。

正确性说明

固定一个数值 $x$ 。程序会枚举每个实际出现的数值 $d$ ，并且仅当 $x$ 是 $d$ 的倍数时，把 frequency[d] 加入 divisor_count[x]。这与条件 $d\mid x$ 完全等价。

因此累加结束后，divisor_count[x] 恰好等于所有数值能整除 $x$ 的牛的数量。对于第 $i$ 头牛，令 $x=A_i$ ，这个集合中包含它自己且只包含一次；减去 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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 11:59
 * update_at: 2026-07-19 14:31
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXV = 1000005;

int n;
int value[MAXN];
int frequency[MAXV];
int divisor_cow_count[MAXV];

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

    cin >> n;
    int maximum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> value[i];
        frequency[value[i]]++;
        if (maximum < value[i]) maximum = value[i];
    }

    // 数值 d 的每头牛，都会被数值为 d,2d,3d,... 的牛拍到。
    for (int divisor = 1; divisor <= maximum; divisor++) {
        if (frequency[divisor] == 0) continue;
        for (int multiple = divisor; multiple <= maximum; multiple += divisor) {
            divisor_cow_count[multiple] += frequency[divisor];
        }
    }

    for (int i = 1; i <= n; i++) {
        // 统计中包含当前牛自己，题目要求只拍其它牛。
        cout << divisor_cow_count[value[i]] - 1 << '\n';
    }
    return 0;
}

复杂度

设最大输入值为 $V$ 。

统计频率和输出答案需要 $O(N)$ 时间。
倍数枚举次数为 $\sum_{d:frequency[d]>0}\lfloor V/d\rfloor$ ，上界可写为 $O(V\log V)$ 。
总时间复杂度为 $O(N+V\log V)$ ，空间复杂度为 $O(N+V)$ 。
brute.cpp 时间复杂度为 $O(N^2)$ ，只用于小数据验证。

总结

本题要复用“相同数值拥有相同答案”。先按值统计频率，再从除数出发把贡献推给所有倍数，就能一次求出每个数值的约数牛总数。最后只减去当前牛自己，重复值对应的其它牛仍会被正确保留。