2020牛客寒假算法基础集训营3——H.牛牛的k合因子数【欧拉筛】

​​题目传送门​​

---

题目描述

合数是指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
牛牛最近在研究 ，所谓 是指一个数的所有因子中，是合数的因子共有k个。
例如 的因子有 ，其中 为合数，它有 个合数因子，就称20是一个
牛牛想要知道 中给定 的情况下

---

输入描述:

第一行输入两个数字表示范围以及查询“k”的数目
接下来m行，每行一个正整数 查询k合因子数的数目。

---

输出描述:

一行一个数字，表示

---

输入

10 5
1
2
3
4
5

---

输出

4
1
0
0
0

---

说明

---

题解

• 欧拉筛过一遍，预处理一下可能用到的数
• 在筛一边合数即可
• 代码注释的挺详细了，很好懂的

---

AC-Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define
const int maxn = 1e5;
const int mod = 1e9 + 7;


int ans[maxn + 7];
int vec[maxn + 7][500]; // 记录因子
int p[maxn + 7]; // 模拟vector，保障vec[i]的因子依次存放
int n, m;

int cnt = 0; //记录已知素数数量
vector<int> primes; //存放素数的不定长数组
bool judge[maxn+7]; //筛除标记
void primes_init() {
cnt = 0;
memset(judge, true, sizeof(judge));
judge[0] = judge[1] = true; // 0和1都不是素数
for (int i = 2; i <= maxn; i++) {
if (judge[i]) {
primes.push_back(i);
cnt++;
}
for (int j = 0; j < cnt && i * primes[j] <= maxn; j++) {
judge[i * primes[j]] = false; //筛除
if (i % primes[j] == 0) //关键代码
break;
}
}
}

void init() {
memset(ans, 0, sizeof ans);
memset(p, 0, sizeof p);
for (int i = 1; i <= maxn; ++i)
for (int j = i; j <= maxn; j += i)
vec[j][p[j]++] = i;
}

int main() {
ios;
while (cin >> n >> m) {
init();
primes_init();
for (int i = 1; i <= n; ++i) {
int ccc = 0; // 合因子数
for (int j = 0; j < p[i]; ++j) // 遍历i的所有因子
if (!judge[vec[i][j]]) // 如果不是素数，即是合数
++ccc;
++ans[ccc]; // 记录答案
}
while (m--) {
int k; cin >> k;
cout << ans[k] << endl;
}
}
return 0;
}

【本文来源：美国服务器 https://www.68idc.cn 复制请保留原URL】