检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
题面
题目描述
给定 个不同的正整数 ,请对 到 每一个 计算,在区间 里有多少正整数是 中恰好 个数的约数。
输入格式
第一行包含两个正整数 ,分别表示区间范围以及 数组的大小。
第二行包含 个不同的正整数 ,表示 数组。
输出格式
输出 行,每行一个整数,其中第 行输出 的答案。
输入输出样例
样例输入 #1
10 3
4 6 7
样例输出 #1
4
4
1
1
样例输入 #2
5 1
8
样例输出 #3
2
3
数据规模与约定
测试点编号 | ||
---|---|---|
1 | ||
2 | ||
3 | ||
4 | ||
5 | ||
6 | ||
7 | ||
8 | ||
9 | ||
10 |
思路
一句话题意:求 中有多少数是 中 个数的约数()。
可以使用 map 存储每一个约数是 中几个数的约数。
然后考虑存储答案,设 表示「是 中 个数的约数」的数的个数。
每当扫到一个约数的时候将 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;
}