2707: 2025AHCPC - 智能制造
金币值：10
定数：13
时间限制：1.000 s
内存限制：128 M
解决：4
提交：4
正确率：100.00% 命题人：
题目描述
在智能制造系统中, $AI$ 需要分析连续生产设备之间的数据兼容性.给定一组设备运行参数序列 $(a_1,a_2,...,a_n)$,请找出最长的连续设备组合,使得相邻设备之间满足工业兼容条件 (即参数具有共同质因数,反应设备间的物理联动关系).
具体来说,设备兼容的关键条件为:
$1.$子序列要求: 设备的前后顺序和原序列中前后顺序一致 (子序列中的两个相邻设备在原序列中不一定相邻).
$2.$兼容性条件: 对于子序列中任意相邻的两个设备参数 $a_i$ 和 $a_j$,满足 $gcd(a_i,a_j) \gt 1$.
输入
第 $1$ 行: 整数 $n \ (1 \le n \le 100000)$,表示生产设备的数量
第 $2$ 行: $n$ 个正整数 $a_i \ (1 \le a_i \le 10^6)$,表示各个生产设备的参数
输出
输出最长的连续设备组合的长度,其中相邻数据满足设备兼容的关键条件.
输入样例1 复制
5
2 4 6 3 9输出样例1 复制
5输入样例2 复制
4
2 3 5 7输出样例2 复制
1