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

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

​​题目传送门​​

题目描述

输入描述:

输出描述:

输入

10 5 1 2 3 4 5

输出

4 1 0 0 0

说明

题解

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

AC-Code

#include using namespace std;typedef long long ll;#defineconst 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 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。