D-小红的子序列_牛客周赛 Round 147

void solve() {
	//数据输入
	int n;
	cin >> n;
	vector<int> a(n + 1);
	int ma = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		//找出最大a[i](方便欧拉筛)
		ma = max(a[i], ma);
	}
	//欧拉筛，筛出所有可能用到的质数
	shai(ma);
	//dp记录每个节点为止的最大符合条件的最大长度；pre记录前驱结点（用于回溯最大子数组）
	vector<int> dp(n + 1), pre(n + 1);
	//每个数组中最靠后的数据的索引
	map<int, int> idx;
	for (int i = 1; i <= n; i++) {
		//初始化该节点
		dp[i] = 1;
		pre[i] = i;
		//找出所有可能的质数因子，并且将dp的值更新
		for (int j = 1; j * j <= a[i]; j++) {
			if (a[i] % j == 0) {
				//必须是质数，而且a[i] / j要在前面的数组中出现
				if (is_primes[j] && idx.find(a[i] / j) != idx.end() && dp[i] < dp[idx[a[i] / j]] + 1) {
					//状态转移，更新父节点
					dp[i] = dp[idx[a[i] / j]] + 1;
					pre[i] = idx[a[i] / j];
				}
				//前一个是(质数因子 <= 根号a[i])这个是(质数因子 >= 根号a[i])原理是一样的
				if (is_primes[a[i] / j] && idx.find(j) != idx.end() && dp[i] < dp[idx[j]] + 1) {
					dp[i] = dp[idx[j]] + 1;
					pre[i] = idx[j];
				}
			}
		}
		//如果idc里面已经有a[i]了，也要再进行覆盖因为这样可以使得子数组可能的值变得更大
		idx[a[i]] = i;
	}
	int f = 0, ii = 0;
	//找到最长子数组大小，并且记录节点
	for (int i = 1; i <= n; i++) {
		if (f <= dp[i]) {
			f = dp[i], ii = i;
		}
	}
	vector<int> ans;
	//回溯输出
	while (pre[ii] != ii) {
		ans.push_back(a[ii]);
		ii = pre[ii];
	}
	ans.push_back(a[ii]);
	cout << ans.size() << endl;
	for (int i = f - 1; i >= 0; i--) {
		cout << ans[i] << ' ';
	}
	cout << endl;
}

bool is_primes[N];
vector<int> primes;

void shai(int n) {
	//初始化所有数都为质数
	fill(is_primes, is_primes + n + 1, true);
	//0和一不是质数，标记一下
	is_primes[0] = is_primes[1] = false;
	//遍历数组
	for (int i = 2; i <= n; i++) {
		//如果is_primes[i]还是true那么i就是质数
		if (is_primes[i]) primes.push_back(i);
		//将所有已经找到的质数全部找出来
		for (int p : primes) {
			//超出范围弹出
			if (1 * i * p > n)break;
			//标记不是质数
			is_primes[i * p] = false;
			//保证每个数只被最小质因子筛一次，这样可以实现线性复杂度
			if (i % p == 0)break;
		}
	}
}