P4394.【数学5】行为权重1
本题为2025年8月24日小红书机考原题
小红书机考的介绍点击这里
题目内容
小红是小红书的用户行为分析师。平台将每次用户行为映射为一个正整数权重序列{a1,a2,...,an}，以便后续关联推荐时提取关键"红色"行为。
为了保证标记的行为具有足够的共性，必须选出的所有“红色”行为权重的最大公约数大于 1 ；同时，为了避免相邻行为产生冗余，所选下标不得相邻。现给定用户的一次行为序列，求最多可以染成红色的行为数量。
[名词解释]
最大公约数:指一组整数共有约数中最大的一个。例如，12、18 和 30 的公约数有 1,2,3,6 ，其中最大的约数是 6 ，因此 gcd(12,18,30)=6 。
输入描述
在一行上输入一个整数 n(1≤n≤105) ,表示行为序列长度。
在第二行输入 n 个整数 a1,a2,…,an(1≤ai≤100) ，表示每次行为的权重值。
输出描述
在一行上输出一个整数，表示最多可染红的行为数量。
样例1
输入
5
1 2 3 2 6
输出
2
说明
样例解释1
在这个样例中，可将下标 2 与 4 对应的权重染红，它们的最大公约数为 2 ，且不相邻，故答案为 2 。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
