思路概述
关键观察
要使被选中的所有权重的最大公约数（GCD）> 1，等价于：存在某个质因子 p>1，使得被选中的每个数都能被 p 整除。
因此，问题可转化为：枚举所有不超过 100 的质数 p，在序列中挑出“能被 p 整除”的位置，要求下标不相邻，并使挑选的个数最大。答案取对所有质数的最大值。
转化为“打家劫舍（House Robber）”DP
题目内容
在一次考古发掘中，考古学家发现了一排 n 块石碑，编号依次为 1 到 n，第 i 块石碑上刻有一个正整数 ai。研究员希望激活若干块石碑进行能量提取，但激活需要遵守以下规则：
- 相邻的石碑不能被同时激活（即不能存在两个编号相邻的石碑均被激活）；
- 所有被激活的石碑上的数字必须是“共振”的。我们称一组正整数是共振的，当且仅当存在一个大于
1 的整数 d，能够同时整除这组中的所有整数。
请问，在满足上述条件下，最多可以激活多少块石碑？
约束：石碑的数量 n 满足 1 ≤ n ≤ 10^5，每块石碑上的数字 ai 满足 1 ≤ a_i ≤ 100。
输入描述
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
