§ 题意简述

在一个序列中选数，使得其GCD大于某个定值，问最多能选几个。

§ 题解

蓝题过了吧。

定义 $dp_{i}$ 为选第 $i$ 个数的情况下前 $i$ 个数的最优答案

方程:

$$dp_{i}=\max_{1\le j<i,\gcd(a_{i},a_{j})\ge L}\{dp_{j}+1\}$$

发现光这样转移的复杂度为n方，T飞。

令 $las_{x}$ 表示约数 $x$ 上次出现的位置。

则方程可以写成：

$$dp_{i}=\max_{j\mid i}\{dp_{las_{j}}+1\}$$

则答案为：

$ANS=\max_{1\le i\le n}\{dp_{i}\}$

#include <cstdio>
#include <algorithm>

using namespace std;

const int Maxn = 1e6 + 5;
int n, L, a[Maxn], dp[Maxn], las[Maxn];

signed main() {
	scanf("%d %d", &n, &L);
	for (int i = 1; i <= n; ++i) 	scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j * j <= a[i]; ++j) {
			if (a[i] % j == 0) {
				int X = j, Y = a[i] / j;
				if (X >= L) {
					dp[i] = max(dp[i], dp[las[X]] + 1);
					las[X] = i;
				}
				if (X != Y) {
					dp[i] = max(dp[i], dp[las[Y]] + 1);
					las[Y] = i;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) 	ans = max(ans, dp[i]);
	return printf("%d\n", ans), 0;
}