上海计算机学会2023年8月月赛C++丙组T4素数行列_素数行列上海算法月赛

素数行列

内存限制: 256 Mb时间限制: 1000 ms

题目描述

给定一个 n×n 的矩阵，其中第 i 行、第 j 列的元素的值为 ai,j​。小爱每次可以花费一点代价，将某个元素的值 +1 。

请问，小爱最少花费多少点代价，才能使得某一行或某一列均为素数？

输入格式

输入第一行，一个正整数 n
接下来 n 行，每行 n 个正整数，其中第 i+1 行，第 j 个元素表示 ai,j​

输出格式

输出共一个整数，表示最小代价

数据范围

• 对于 30% 的数据， 1≤n≤10
• 对于 60% 的数据， 1≤n≤10^2，1≤ai,j​≤10^2
• 对于 100% 的数据， 1≤n≤10^3，1≤ai,j​≤10^5

样例数据

输入:
3
5 4 3
1 7 8
9 2 6
输出:
1
说明:
花费一点代价把4改成5，第二列均为素数
 

解析：先用埃氏筛法求出一百万以内的素数，然后逐行逐列，求出大于等于aij最小的素数，求和的最小值，即为答案，详见代码。

#include<bits/stdc++.h>
using namespace std;
int n;
bool s[1000005];
int ss[100005];
int a[1005][1005];
int len=0;
int ans=1e9;
int main() {
    for (int i=2;i<=1000;i++){//埃氏筛求出1000000以内的所有素数
        if (s[i]==0){
            for (int j=i*i;j<=1000000;j+=i){
                s[j]=1;
            }
        }
    }
    for (int i=2;i<=1000000;i++){//把这些素数转移到ss数组中，便于后边二分查找
        if (s[i]==0){
            len++;
            ss[len]=i;
        }
    }
    cin>>n;
    for(int i=1;i<=n;i++){//输入
        for (int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){//对于每一行每一列计算需要增加的数
        int hsum=0;//第i行需要增加的数
        int lsum=0;//第i列需要增加的数
        for (int j=1;j<=n;j++){
            //找到大于等于第i行第j列的数的最小素数，算出需要最小增加的数
            hsum+=ss[lower_bound(ss,ss+len,a[i][j])-ss]-a[i][j];
            //找到大于等于第j行第i列的数的最小素数，算出需要最小增加的数
            lsum+=ss[lower_bound(ss,ss+len,a[j][i])-ss]-a[j][i];
        }
        //所有行列的最小值就是答案
        ans=min(ans,hsum);
        ans=min(ans,lsum);
    }
    cout<<ans;
    return 0;
}