题目:
题意:给你一个递增序列,然后找出满足两点要求的最长子序列
第一点是a[i]>a[i-1]
第二点 gcd(a[i],a[i-1])>1 也就是说两个数不能互质
找出最长的子序列长度
思路:首先想互质问题,如果两个数互质说明两个数之间没有素因子相同,我们想以每个素因子结尾的最大长度是多少
然后比如样例 2 3 4 6 9
第一个数 2 2结尾 1
第二个数 3 3结尾 1
第三个数 4 2结尾 2
第四个数6 拆分因子有 2,3 2结尾 3, 3结尾2 ,但是这个时候我以6结尾,那么其实3这个位置长度也是3了,
(所以,我们要找出最大的那个长度,再重新赋值到这个数的每个素因子上) 这个时候就能解出来了
#include#include #include #include #include #include #include