1 条题解
-
0
题目大意
对每个位置,统计严格位于其右侧的不同素数的个数。
解题思路
从右往左扫描。处理一个位置前,
count正好是其右侧出现过的不同素数的个数,所以先记录它。然后检查当前数。如果它是尚未标记的素数,就标记并给计数加一,供下一轮使用。输出时按下标从小到大读取答案。设数值上界为 ,试除只需枚举到平方根,时间复杂度为 ,空间复杂度为 。易错点
易错点 说明 先更新计数再记录答案 当前元素只影响它左边位置的答案。 同一种素数出现多次就完全不计 每种素数计一次,用 seen去重。把 1 当作素数或用负数访问数组 先判断当前数是否至少为 2。 试除循环漏掉平方根 循环条件用 factor * factor <= value,从而识别 49 等完全平方数。参考代码
#include <stdio.h> static unsigned char seen[100001]; int is_prime(int value) { if (value < 2) { return 0; } for (int factor = 2; factor * factor <= value; ++factor) { if (value % factor == 0) { return 0; } } return 1; } int main(void) { int n, values[10000], answers[10000]; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &values[i]); } int count = 0; for (int i = n - 1; i >= 0; --i) { answers[i] = count; int value = values[i]; if (value >= 2 && !seen[value] && is_prime(value)) { seen[value] = 1; ++count; } } for (int i = 0; i < n; ++i) { printf("%d%c", answers[i], i + 1 == n ? '\n' : ' '); } return 0; }
信息
- ID
- 653
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 93
- 已通过
- 19
- 上传者
吉公网安备22010402001496号