DP Good Sequences

给N个升序的数字，要求找出一个子串，每相邻两个数字不互质，求最长串的长度

提示

1）dp[i]表示到第i个数字的最长串

2）dp[i]用前i-1项中与第i项不互质的最大项更新

3）寻找与第i项不互质，即找与第i项有公公因数，所以建立数组dig[i]表示该因数出现的次数

#include 
  
   
#include 
   
     #define maxn 100005 int dp[maxn]; int dig[maxn]; int mark[maxn]; int gcd(int a,int b) { int k; while(b!=0) { k=a%b; a=b; b=k; } return a; } int max(int a,int b) { return a