正确的

显而易见的是dp dp dp dp

对于每个条件我们挨个看 对于条件一

对于任意的 i(1≤i<m)，满足 b_i​</sub><b_i+1​</sub>。

sort秒了，下一题

对于任意的 i(1≤i<m)，满足 gcd(bi,b_i+1​)>1。其中，gcd(x,y)为x和y的最大公因数，即最小的d**，满足：d∣x且d∣y。 ​ 对于任意的 i(1≤i≤m)，b_i这个数是好的。

条件三秒了，下一题

对于条件二的筛选 我们可以先把素数给bamn了 当然是我们的线性筛

void f()
{
	for(long long i=2;i<N;i++)
		if(!vis[i])
		{
			p.push_back(i);
			for(long long j=i*i;j<N;j+=i)
				vis[j]=1;
		}
}//筛素数

同时我们用p记录素数 众所粥汁儿 所有数字（除去1）都可以用素数之积来表示 所以我们没有必要找到两个数字的最大公因数 只要有一个不为1的其他因数相同 那就一定满足条件二

但是也会因此而出现分歧 给出的a 数组不一定能够全部用上 这将会存在最优解 这就是一个dp了 （个人感觉有导弹拦截的味儿

我们从小到大去进行dp 因为对于任意b_i+1>b_i 且两者符合三个条件 存在ans[i+1],ans[i] 那么ans[i+1]一定是在ans[i]的基础上+1的

该按什么顺序去遍历呢？？？ 刚刚存的q就可用了

Coke

#include <iostream>
#include <unordered_map>
#include <algorithm> 
#include <vector>
using namespace std;

const int N=100014;
int vis[N],t,n,ans;
vector<int> p;

void f()
{
	for(long long i=2;i<N;i++)
		if(!vis[i])
		{
			p.push_back(i);
			for(long long j=i*i;j<N;j+=i)
				vis[j]=1;
		}
}//筛素数 

int main()
{
	
	f();
	scanf("%d",&t);
	
	while(t--)
	{
		scanf("%d",&n);
		vector<int> a(n);
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		
		sort(a.begin(),a.end());//排序满足条件一 
		
		vector<int> dp(n,1);
		unordered_map<int,int> mp;//mp有序会TLE哦~
		ans=1;
		for(int i=0;i<n;i++)
		{
			int val=a[i];
			for(int fact:p)
			{
				if(val<=1)
					break;
				if(val%fact==0)
				{
					if(mp.count(fact)>0)
					{
						int x=mp[fact];
						dp[i]=max(dp[i],dp[x]+1);
					}
					mp[fact] = i;
					while(val%fact==0)
						val/=fact;
				}
			}
			ans = max(ans,dp[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}