『题解』CodeForces CF271B Prime Matrix
仙山有茗
·
·
题解
题目传送门
题目大意
给定一个 n \times m 的由整数构成的矩阵，每次操作可以将一个数 +1，求将任意一行或一列的数全变为质数的最小操作次数。
# 思路
首先使用欧拉筛把质数都筛出来，为了保险，直接筛 $1 \sim 2 \times 10^5$。
对于 $a_{i,j}(1 \le i \le n,1 \le j \le m)$，暴力计算出操作多少次可以变为质数。
最后跑两次二维循环计算行、列操作总和，取 $\min$ 即可。
# 代码
```cpp
#include <iostream>
using namespace std;
template<typename T=int>
inline T read(){
T X=0; bool flag=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+(ch^48),ch=getchar();
if(flag) return X;
return ~(X-1);
}
const int N=5e2+5,M=2e5+5;
int n,m,sum,ans=0x3f3f3f3f;
int a[N][N],f[N][N];
int prime[M],isprime[M];
// 欧拉筛
template<typename T=int>
int getprime(T n){
int cnt=0;
for(int i=1; i<=n; i++) isprime[i]=1;
isprime[1]=0;
for(int i=2; i<=n; i++){
if(isprime[i]) prime[++cnt]=i;
for(int j=1; j<=cnt && prime[j]*i<=n; j++){
isprime[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
return cnt;
}
int main(){
n=read(),m=read();
getprime(2e5);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(a[i][j]=read(); !isprime[a[i][j]+f[i][j]]; f[i][j]++);
/* 这一句相当于：
a[i][j]=read();
while(!isprime[a[i][j]])
a[i][j]++,f[i][j]++;
*/
// 每列
for(int i=1; i<=n; i++,ans=min(ans,sum),sum=0) // 直接把取 min 和重置写到循环里
for(int j=1; j<=m; j++)
sum+=f[i][j];
// 每行
for(int i=1; i<=m; i++,ans=min(ans,sum),sum=0)
for(int j=1; j<=n; j++)
sum+=f[j][i]; // 注意这里 j 和 i 要反过来，i 是行数
printf("%d\n",ans);
return 0;
}
```