[语言月赛 202309] 悬线

题目背景

我们定义一个数字是质数，当且仅当它的因子仅有 $1$ 和自身。特别的，$1$ 不是质数。

题目描述

给定一个 $n\times m$ 的数字阵。约定第 $i$ 行第 $j$ 列上的数用 $(i,j)$ 表示。

我们称以第 $i$ 行第 $j$ 列的格子为底的悬线的长度是最大的 $k$，满足 $k\le i$ 且 $(i,j),(i-1,j),(i-2,j),\dots (i-k+1,j)$ 这 $k$ 个数都是质数。特别的，如果 $(i,j)$ 本身不是质数，称以第 $i$ 行第 $j$ 列为底的悬线长度为 $0$。

对于每个格子，请你求出以它为底的悬线长度。

输入格式

本题单个测试点内有多组测试数据。输入的第一行是一个整数，表示数据组数 $T$。

对每组数据，按如下格式输入：

每组数据第一行是两个整数，表示数字阵的行数 $n$ 和列数 $m$。
接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $(i,j)$。

输出格式

对每组数据，输出 $n$ 行，每行 $m$ 个用单个空格隔开的整数。第 $i$ 行第 $j$ 个数表示以第 $i$ 行第 $j$ 列的格子为底的悬线长度。

样例 #1

样例输入 #1

1
3 3
1 2 3
4 5 6
7 8 9

样例输出 #1

0 1 1
0 2 0
1 0 0

提示

数据规模与约定

• 对 $20\%$ 的数据，$n=1$。
• 对 $50\%$ 的数据，$(i,j)\le 100$。
• 对 $80\%$ 的数据，$(i,j)\le 1000$。
• 对 $100\%$ 的数据，$1\le n,m\le 200$，$1\le (i,j)\le 10^5$，$1\le T\le 15$。

C++实现

#include <bits/stdc++.h>
using namespace std;
int t, n, m, a[210][210], f[210][210];
bool prime(int n){
if(n == 1) return 0;
if(n == 2) return 1;
for(int i = 2; i <= sqrt(n); i ++)
if(n % i == 0) return 0;
return 1;
}
int main(){
cin >> t;
while(t --){
memset(f, 0, sizeof f);
cin >> n >> m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(prime(a[i][j]))
f[i][j] = f[i - 1][j] + 1;
else
f[i][j] = 0;
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cout << f[i][j] << " ";
}
cout << endl;
}
}
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容