Skip to content

S2OJ - 90. Divisors

题解485 字
# S2OJ # 数学 # 雅礼集训
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

给定 mm 个不同的正整数 a1,a2,...,ama_1, a_2, ..., a_m ，请对 00 到 mm 每一个 kk 计算，在区间 [1,n][1, n] 里有多少正整数是 aa 中恰好 kk 个数的约数。

#输入格式

第一行包含两个正整数 n,mn, m ，分别表示区间范围以及 aa 数组的大小。

第二行包含 mm 个不同的正整数 a1,a2,...,ama_1, a_2, ..., a_m ，表示 aa 数组。

#输出格式

输出 m+1m + 1 行，每行一个整数，其中第 ii 行输出 k=ik = i 的答案。

#输入输出样例

样例输入 #1

10 3
4 6 7

样例输出 #1

4
4
1
1

样例输入 #2

5 1
8

样例输出 #3

2
3

#数据规模与约定

测试点编号 nn mm
1 55 ≤1000\leq 1000
2 5050
3 200200
4 11 ≤109\leq 10^9
5
6
7 200200
8
9
10

#思路

一句话题意：求 [1,n][1, n] 中有多少数是 ai∼ama_i \sim a_m 中 kk 个数的约数（k∈[1,m]k \in [1, m]）。

可以使用 map 存储每一个约数是 a1∼aia_1 \sim a_i 中几个数的约数。

然后考虑存储答案，设 sumjsum_j 表示「是 a1∼aia_1 \sim a_i 中 jj 个数的约数」的数的个数。

每当扫到一个约数的时候将 sum[b[j]]--, sum[++b[j]]++ 即可。

#代码

C++
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
#include <bits/stdc++.h>

using namespace std;

int n, m, a[205], sum[205];
map<int, int> b;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    sum[0] = n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j * j <= a[i] && j <= n; j++) {
            if (a[i] % j == 0) {
                sum[b[j]]--;
                sum[++b[j]]++;
                if (j * j != a[i] && a[i] / j <= n) {
                    sum[b[a[i] / j]]--;
                    sum[++b[a[i] / j]]++;
                }
            }
        }
    }
    for (int i = 0; i <= m; i++) {
        cout << sum[i] << endl;
    }
    return 0;
}