1 条题解

  • 0
    @ 2026-11-11 20:46:31

    题目大意

    对每个位置,统计严格位于其右侧的不同素数的个数。

    解题思路

    从右往左扫描。处理一个位置前,count 正好是其右侧出现过的不同素数的个数,所以先记录它。然后检查当前数。如果它是尚未标记的素数,就标记并给计数加一,供下一轮使用。输出时按下标从小到大读取答案。设数值上界为 MM,试除只需枚举到平方根,时间复杂度为 O(nM)O(n\sqrt{M}),空间复杂度为 O(n+M)O(n+M)。

    易错点

    易错点 说明
    先更新计数再记录答案 当前元素只影响它左边位置的答案。
    同一种素数出现多次就完全不计 每种素数计一次,用 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;
    }
    
    • 1

    信息

    ID
    653
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    93
    已通过
    19
    上传者