S2OJ - 90. Divisors

题面

题目描述

给定 $m$ 个不同的正整数 $a_1, a_2, ..., a_m$ ，请对 $0$ 到 $m$ 每一个 $k$ 计算，在区间 $[1, n]$ 里有多少正整数是 $a$ 中恰好 $k$ 个数的约数。

输入格式

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

第二行包含 $m$ 个不同的正整数 $a_1, a_2, ..., a_m$ ，表示 $a$ 数组。

输出格式

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

输入输出样例

样例输入 #1

10 3
4 6 7

样例输出 #1

4
4
1
1

样例输入 #2

5 1
8

样例输出 #3

2
3

数据规模与约定

思路

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

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

然后考虑存储答案，设 $sum_j$ 表示「是 $a_1 \sim a_i$ 中 $j$ 个数的约数」的数的个数。

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

代码

#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;
}