P5427. 质因数跳跃

场次：2026年9月11日-非AI方向 · 来源：CodeFun2000 P5427

题目描述

有一个非空正整数序列 $seq$，长度记为 $m$。一开始位置 $p$ 停在下标 $0$。随后 $p$ 可以跳到 $p+d$ 或 $p-d$，但必须满足 $p+d \le m-1$ 且 $p-d \ge 0$。这里的 $d$ 取当前格子 $seq_p$ 的质因数；若该格子为 $1$，则不存在可用的 $d$，位置无法再跳。问能否按这条规则让 $p$ 恰好落到最后一个下标。

质因数：某个正整数的因数里那些质数。整数 $1$ 不含于任何数的质因数集合。

举例来说，$12$ 可以分解出质因数 $2$、$3$。

输入格式

一行若干正整数，用空格隔开，即整个序列，例如

1 2 3 4

满足 $1 \le m \le 10^{4}$，$1 \le seq_p \le 10^{3}$。

输出格式

若位置能够落到序列末位，输出 true

否则输出 false

示例

示例 1

输入：

4 1 1 9

输出：

false

说明：

起点为 $4$，质因数只有 $2$，只能跳到下标 $2$；该处为 $1$，无法再跳，到不了下标 $3$。

示例 2

输入：

10 1 4 9 1

输出：

true

说明：

$10$ 的质因数是 $2$ 与 $5$。从下标 $0$ 沿 $2$ 跳到下标 $2$（值为 $4$）。

$4$ 的质因数是 $2$，再沿 $2$ 跳到最后一个下标。

示例 3

输入：

1 6 8

输出：

false

说明：

起点为 $1$，没有质因数，位置无法离开下标 $0$，而末位是下标 $2$。