Skip to content

S2OJ - 90. Divisors

题解498 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

给定 mm 个不同的正整数 a1,a2,...,ama_1, a_2, ..., a_m ,请对 00mm 每一个 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] 中有多少数是 aiama_i \sim a_mkk 个数的约数(k[1,m]k \in [1, m])。

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

然后考虑存储答案,设 sumjsum_j 表示「是 a1aia_1 \sim a_ijj 个数的约数」的数的个数。

每当扫到一个约数的时候将 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;
}