思路概述

关键观察

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

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

本题为2025年8月24日小红书机考原题

小红书机考的介绍点击这里

题目内容

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

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

[名词解释]

最大公约数:指一组整数共有约数中最大的一个。例如，$12、18$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此 $gcd(12,18,30)=6$ 。

输入描述

在一行上输入一个整数 $n(1≤n≤10^5)$ ,表示行为序列长度。

在第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤100)$ ，表示每次行为的权重值。

输出描述

在一行上输出一个整数，表示最多可染红的行为数量。

样例1

输入

5
1 2 3 2 6

输出

2

说明

样例解释1

在这个样例中，可将下标 $2$ 与 $4$ 对应的权重染红，它们的最大公约数为 $2$ ，且不相邻，故答案为 $2$ 。