思路概述
关键观察
要使被选中的所有数字的最大公约数（GCD）> 1，等价于：存在某个质因子 p>1，使得被选中的每个数都能被 p 整除。
因此，问题可转化为：枚举所有不超过 100 的质数 p，在序列中挑出“能被 p 整除”的位置，要求下标不相邻，并使挑选的个数最大。答案取对所有质数的最大值。
转化为“打家劫舍（House Robber）”DP
题目内容
小蓝有一些标有正整数的卡片，排成一排。他想从中挑选尽可能多的卡片，但需要遵守两条规则：
- 选中的任意两张卡片在排列中不能相邻。
- 存在一个大于 1 的整数 d，使得所有被选中的卡片上的数字都能被 d 整除。
请问，小蓝最多能挑选多少张卡片？
序列的长度 n 满足 n≤105，每张卡片上的整数 ai 满足 ai≤100。
输入描述
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
