2025-12 · 5级 · 相等序列

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1250 字

CCF 原卷官方标程 · 质数 · 本地编译通过

2025-12
质数

正文

// GESP 2025-12 C++ 5级 编程题 2 · 相等序列
// 原题：https://oj.yecheng.tv/p/gs2512l5p2
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1727912539586592.pdf
// 题意：小 A 有一个包含个正整数的序列 。
// 知识点：质数
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 1/1 通过
//
#include <iostream>
using namespace std;
const int N = 100010;
int num[N][20];
int n, a[N];
void calc_prime_factor(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            int cnt=0;
            while(x%i==0){
                x/=i;
                cnt++;
            }
            num[i][cnt]++;
        }
    }
    if(x>1){
        num[x][1]++;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        calc_prime_factor(a[i]);
    }
    long long ans=0;
    for(int i=2;i<100001;i++){
        int pos = 0;
        for(int j=0;j<20;j++){
            pos += num[i][j];
        }
        num[i][0]=n-pos;
        int median_exponent=0;
        pos = 0;
        for(int j=0;j<20;j++){
            pos += num[i][j];
            if(pos*2>=n){
                median_exponent=j;
                break;
            }
        }
        for(int j=0;j<20;j++){
            ans+=num[i][j]*abs(j-median_exponent);
        }
    }
    printf("%lld\n",ans);
}

2025-12 · 5级 · 相等序列

正文

GESP 标程 · 考级真题的其它内容