题目内容

在一个信号监测系统中，记录了一系列信号强度 $a_1, a_2, \dots, a_n$，均为正整数。现在需要从中挑选出一组信号进行重点分析，要求如下：

• 任何两个被选中的信号在序列中不能相邻（即如果选中了 $a_i$，则不能选中 $a_{i-1}$ 和 $a_{i+1}$）。
• 所有被选中信号强度的最大公约数必须大于 $1$。

请计算最多能选出多少个信号满足上述条件。

序列长度 $n$ 不超过 $10^5$，每个信号强度 $a_i$ 为不超过 $100$ 的正整数。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写