思路概述

关键观察

要使被选中的所有权重的最大公约数（GCD）> 1，等价于：存在某个质因子 $p>1$，使得被选中的每个数都能被 $p$ 整除。 因此，问题可转化为：枚举所有不超过 100 的质数 $p$，在序列中挑出“能被 $p$ 整除”的位置，要求下标不相邻，并使挑选的个数最大。答案取对所有质数的最大值。

转化为“打家劫舍（House Robber）”DP

对固定的质数 $p$，构造二值数组：

题目内容

小红是小红书的用户行为分析师。平台将每次用户行为映射为一个正整数权重序列{$a_1,a_2,...,a_n$}，以便后续关联推荐时提取关键"红色"行为。

为了保证标记的行为具有足够的共性，必须选出的所有“红色”行为权重的最大公约数大于 $1$ ；同时，为了避免相邻行为产生冗余，所选下标不得相邻。现给定用户的一次行为序列，求最多可以染成红色的行为数量。