[语言月赛 202309] 悬线

Luogu
IDLGB3858
Time1000ms
Memory512MB
DifficultyP2
2023O2优化数组语言月赛
给定一个 $n \times m$ 的数字阵。约定第 $i$ 行第 $j$ 列上的数用 $(i,j)$ 表示。 我们称以第 $i$ 行第 $j$ 列的格子为底的**悬线**的长度是最大的 $k$,满足 $k \leq i$ 且 $(i,j), (i-1,j), (i-2,j),\dots(i-k+1,j)$ 这 $k$ 个数都是**质数**。特别的,如果 $(i, j)$ 本身不是质数,称以第 $i$ 行第 $j$ 列为底的悬线长度为 $0$。 对于每个格子,请你求出以它为底的悬线长度。 ## Input **本题单个测试点内有多组测试数据**。输入的第一行是一个整数,表示数据组数 $T$。 对每组数据,按如下格式输入: 每组数据第一行是两个整数,表示数字阵的行数 $n$ 和列数 $m$。 接下来 $n$ 行,每行 $m$ 个整数,第 $i$ 行第 $j$ 个整数表示 $(i,j)$。 ## Output 对每组数据,输出 $n$ 行,每行 $m$ 个用单个空格隔开的整数。第 $i$ 行第 $j$ 个数表示以第 $i$ 行第 $j$ 列的格子为底的悬线长度。 [samples] ## Background 我们定义一个数字是质数,当且仅当它的因子仅有 $1$ 和自身。特别的,$1$ 不是质数。 ## Note ### 数据规模与约定 - 对 $20\%$ 的数据,$n = 1$。 - 对 $50\%$ 的数据,$(i,j) \leq 100$。 - 对 $80\%$ 的数据,$(i,j) \leq 1000$。 - 对 $100\%$ 的数据,$1 \leq n, m \leq 200$,$1 \leq (i,j) \leq 10^5$,$1 \leq T \leq 15$。
Samples
Input #1
1
3 3
1 2 3
4 5 6
7 8 9
Output #1
0 1 1
0 2 0
1 0 0
API Response (JSON)
{
  "problem": {
    "name": "[语言月赛 202309] 悬线",
    "description": {
      "content": "给定一个 $n \\times m$ 的数字阵。约定第 $i$ 行第 $j$ 列上的数用 $(i,j)$ 表示。 我们称以第 $i$ 行第 $j$ 列的格子为底的**悬线**的长度是最大的 $k$,满足 $k \\leq i$ 且 $(i,j), (i-1,j), (i-2,j),\\dots(i-k+1,j)$ 这 $k$ 个数都是**质数**。特别的,如果 $(i, j)$ 本身不是质数,称以第 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3858"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $n \\times m$ 的数字阵。约定第 $i$ 行第 $j$ 列上的数用 $(i,j)$ 表示。\n\n我们称以第 $i$ 行第 $j$ 列的格子为底的**悬线**的长度是最大的 $k$,满足 $k \\leq i$ 且 $(i,j), (i-1,j), (i-2,j),\\dots(i-k+1,j)$ 这 $k$ 个数都是**质数**。特别的,如果 $(i, j)$ 本身不是质数,称以第 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments