//CodeForces 264B
//分析：在数列上的 dp，选取前缀集合的大小作为下标很容易构造出一个 O(n^2) 的 dp，i > j,if(ans[i]与ans[j]之间具有相同的素因子) dp[i] = max(dp[j]+1)，不过 n 有100000那么大，于是继续优化，dp[i]表示以 ans[i] 结尾的最长的 good sequence 的长度
//思路：因为每次都求 ans[i] 和 ans[j] 之间是否具有相同的素因子显然太过蛋疼，于是我们就顺着素因子的方向考虑这个dp。我们把每个数字都进行素数分解，于是 dp[i] 就变成了几个 dp[prime]，dp[prime] 表示：对于某个具有此 prime 作为因子的 ans[i]，以 ans[i] 作为某个 good sequence 的最后一个元素时对应的最长序列长度，这样我们就只需要将整个 ans 遍历一次，同时分解每一个ans[i]，然后去维护 dp[prime] 就好了
1 #include"iostream" 2 #include"cstdio" 3 using namespace std; 4 const int maxn = 100010; 5 int tot,prime[maxn],min_prime[maxn]; //筛素数，素数结果存在 prime 中，一个数的最小素因子存在 min_prime 中 6 int n,ans,prefix_prime_len[maxn],f_tot,factor[maxn]; //prefix_prime_len[maxn] 即 dp[prime]。因为将 ans[i] 分解成了素因子，所以使得我们不用辛苦的去求任意两个元素之间的素因子了，每次把 ans[i] 的素因子全部求出，然后维护这些素因子的性质即可 7 int main() 8 { 9 int i,j,max_len; 10 tot = 0; 11 for(i = 2; i<maxn; ++i) 12 min_prime[i] = i; 13 for(i = 2; i<maxn; ++i) { 14 if(i==min_prime[i]) { //若 i 为质数 15 prime[++tot] = i; 16 } 17 for(j = 1; j<=tot&&i*prime[j]<maxn; ++j) { //i 充当 倍数 18 min_prime[i*prime[j]] = prime[j]; 19 if(min_prime[i]==prime[j]) { //若 i 的最小素因子为当前素数（即i 中具有一个比下一个素数更小的素因子） 20 break; 21 } 22 } 23 } 24 scanf("%d",&n); 25 for(i = 1; i<=n; ++i) { 26 scanf("%d",&ans); 27 f_tot = 0; 28 while(ans!=1) { //具体实现过程分两步，将 ans[i] 进行素数分解，将这些素因子对应的 dp 值更新成一样的值 29 factor[++f_tot] = min_prime[ans]; 30 ans /= factor[f_tot]; 31 while(ans % factor[f_tot]==0) { 32 ans /= factor[f_tot]; 33 } 34 } 35 max_len = prefix_prime_len[factor[1]]; 36 for(j = 2; j<=f_tot; ++j) { 37 if(max_len<prefix_prime_len[factor[j]]) 38 max_len = prefix_prime_len[factor[j]]; 39 } 40 for(j = 1; j<=f_tot; ++j) { 41 prefix_prime_len[factor[j]] = max_len+1; 42 } 43 } 44 max_len = 1; //如果输入的 ans[i] 全部为 1，那么 1 显然是无法分解成素数的，但是这种情况下应该要输出 1 45 for(i = 1; i<=tot; ++i) { 46 if(max_len<prefix_prime_len[prime[i]]) 47 max_len = prefix_prime_len[prime[i]]; 48 } 49 printf("%d ",max_len); 50 }