「一本通 6.2 练习 2」轻拍牛头

题目描述

$N$ 头奶牛各持数字 $A_i$ ，每头牛拍打所有持有 $A_i$ 约数的牛（不含自己）。输入第一行 $N$ ，接下来 $N$ 行每行一个 $A_i$ ；输出 $N$ 行答案。 $1 \le N \le 10^5$ ， $1 \le A_i \le 10^6$ 。样例输入 5 / 2 1 2 3 4，样例输出 2 0 2 1 3。

思路

统计每个数字出现次数 cnt，让每个出现过的数字 $d$ 向自己的所有倍数广播 cnt[d]，得到 div_sum[v] 表示能整除 $v$ 的数字个数（含自己），答案为 div_sum[A_i] - 1。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 22:32
# update_at: 2026-09-30 22:35

import sys


def divisor_sums(cards: list[int]) -> list[int]:
    """div_sums[v] = 有多少头牛的数字整除 v（含「自己整除自己」这一份）。"""
    max_a = max(cards)
    cnt = [0] * (max_a + 1)
    for a in cards:
        cnt[a] += 1

    div_sums = [0] * (max_a + 1)
    for d in range(1, max_a + 1):
        c = cnt[d]
        if c:  # 只让出现过的数字向自己的所有倍数广播，总步数是调和级数 O(M log M)
            for multiple in range(d, max_a + 1, d):
                div_sums[multiple] += c
    return div_sums


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    cards = [next(data) for _ in range(n)]

    div_sums = divisor_sums(cards)
    # 自己的数字整除自己，每个询问都被多算了 1，扣掉
    print('\n'.join(str(div_sums[a] - 1) for a in cards))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-06 01:18
 * update_at: 2026-10-06 01:18
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXM = 1000000; // 值域上限

int n;
int a[100005];            // 每头奶牛的数字
int cnt[MAXM + 5];        // cnt[v] 表示数字 v 出现的次数
int div_sum[MAXM + 5];    // div_sum[v] 表示有多少个数字能整除 v（含自己）

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

    cin >> n;
    int max_a = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        cnt[a[i]]++;
        if (a[i] > max_a) max_a = a[i];
    }

    // 对每个出现过的数字 d，把 cnt[d] 广播到 d 的所有倍数上
    for (int d = 1; d <= max_a; ++d) {
        if (cnt[d] == 0) continue;
        for (int multiple = d; multiple <= max_a; multiple += d) {
            div_sum[multiple] += cnt[d];
        }
    }

    // 自己整除自己多算了 1，输出时扣掉
    for (int i = 1; i <= n; ++i) {
        cout << div_sum[a[i]] - 1 << "\n";
    }
    return 0;
}

「一本通 6.2 练习 2」轻拍牛头

目录

题目描述

思路

参考代码