Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a1,?a2,?...,?an are good.
Now she is interested in good sequences. A sequence x1,?x2,?...,?xk is called good if it satisfies the following three conditions:
- The sequence is strictly increasing, i.e. xi?<?xi?+?1 for each i (1?≤?i?≤?k?-?1).
- No two adjacent elements are coprime, i.e. gcd(xi,?xi?+?1)?>?1 for each i (1?≤?i?≤?k?-?1) (where gcd(p,?q) denotes the greatest common divisor of the integers p and q).
- All elements of the sequence are good integers.
Find the length of the longest good sequence.
The input consists of two lines. The first line contains a single integer n (1?≤?n?≤?105) — the number of good integers. The second line contains a single-space separated list of good integers a1,?a2,?...,?an in strictly increasing order (1?≤?ai?≤?105; ai?<?ai?+?1).
Print a single integer — the length of the longest good sequence.
5 2 3 4 6 9
4
9 1 2 3 5 6 7 8 9 10
4
In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.
【题解】 题意是给定一个长度为n的序列，这个序列是严格递增的，要在这个序列里面找一个最长不互质子序列，这里的不互质是指相邻两个不互质。
这道题本来是用dp+gcd做的，但是和明显超时了，题目数据量是100000，而且测试数据也达到了97000多组，这种方法果然超时，那该怎么做呢？我们不妨换一种思路，我们用GCD的目的就是判断两个数的最大公因数是不是1，既然是找公因数，那我们就可以提前把他们的因数都列出来（打表）。如下图，样例一过程模拟：
这个就是init函数打表过程，样例为2,3,4,6,9，读者最好自己动手模拟一下，2的因子只有2，2的因子2的右下标为1，表示2这个因子出现第一次，继续往后，3的因子也是第一次出现，所以也为1，到4后，因为4的因子有2，而2已经出现过1次，所以这个因子数表为2，为什么因子4的下标也是2呢，因为4是这个序列的第二个数了，那自然4的所有因子下标都应该是2了（这里仔细想想，想通了），再往后，6有因子2,3,因为我们要找的是最长的序列，而恰好下标的数就代表着序列的长度，所以在6之前2的下标是2,3的下标是1，我们就选择2的下标来更新6的所有因子下标，这就是以这些因子结尾的序列的长度，9也是一样的过程，可以看到，到9的时候因为前面的因子3下标是3，是最大的，所以更新后9的所有因子下标就是4了，答案就是4了，最后还要遍历找最大值，这个看代码。
相信读者已经对这个做法有一定理解了吧，继续加油！
【AC代码】
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#define maxn 100050
using namespace std;
vector<int>vc[maxn];
void init()
{int i,j;for(i=2;i<maxn;i++){for(j=i;j<maxn;j+=i)vc[j].push_back(i);}
}
int a[maxn],dp[maxn];
int main()
{init();int n;while(scanf("%d",&n)!=EOF){int i;vector<int>::iterator it;memset(dp,0,sizeof(dp));for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<=n;i++){int temp=0;for(it=vc[a[i]].begin();it!=vc[a[i]].end();it++){temp=max(temp,dp[*it]); //选出所有因子中下标最大的}for(it=vc[a[i]].begin();it!=vc[a[i]].end();it++){dp[*it]=temp+1;//用最大的下标更新所有a[i]的因子}}int ans=1;for(i=0;i<maxn;i++)//遍历找到最大值ans=max(ans,dp[i]);printf("%d\n",ans);}
}