靠。。刚想出这道题Vijos居然奔溃了。。我哭啊。。
题目是说给你n个数，都小于10^5，然后让你求出其中一个子序列（连不连续无所谓，只要顺序是原序列的顺序就OK）。。相邻两个数不互质。。让你求这个序列的最大长度。。n<=100000
很明显暴力DP是会悲剧的，如果你用Dpi表示第i个数结尾的最长长度然后O(n)枚举前一个的话是O(n^2)的。关键是利用题目的性质。
注意到不互质的数一定有一个公共的质因子，就简单了。首先算出10^5一下每个质数，然后开个数组保存每个当前以第i个质数的倍数结尾的数列的最长值，然后对于每个数枚举他的每个质因子计算并更新一下就可以了。。
关键是一个数的质因子数目显然是O(logn)级别的，并且预先处理也可以大大降低枚举量。。程序还是很快的。。
不过VJ挂了。没法测了囧。。