题目地址：洛谷：【P4411】[BJWC2010]取数游戏 – 洛谷、BZOJ：Problem 1978. — [BeiJing2010]取数游戏 game

题目描述

小 C 刚学了辗转相除法，正不亦乐乎，这小 P 又出来捣乱，给小 C 留了个 难题。 给 N 个数，用 a1,a2…an来表示。现在小 P 让小 C 依次取数，第一个数可以 随意取。假使目前取得 aj，下一个数取ak(k>j)，则ak必须满足gcd(aj,ak)≥L。 到底要取多少个数呢？自然是越多越好！ 不用多说，这不仅是给小 C 的难题，也是给你的难题。

输入输出格式

输入格式：
第一行包含两个数N 和 L。 接下来一行，有 N 个数用空格隔开，依次是 a1,a2…an。

输出格式：
仅包含一行一个数，表示按上述取法，最多可以取的数的个数。

输入输出样例

输入样例#1：

5 6
7 16 9 24 6 

输出样例#1：

3

说明

选取 3个数16、24、6。gcd(16,24)=8，gcd(24,6)=6。
2≤L≤ai≤1 000 000；
30% 的数据N≤1000；
100% 的数据 N≤50 000

题解

我们用一种类似LIS的DP思路，用dp[i]表示以i结尾最多能选多少个数，有以下转移
dp[i] = \max_{j|a_i, j \geq l} \{ dp[lst_j] \}
其中lst_i表示含因数i的数最后一次出现的位置。易知对于每一个因数，含它的数的位置越靠后，dp值是不降的，因此转移成立。枚举因数转移一下即可。
复杂度O(n \sqrt{n})。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1000005;

int n, l, a[MAXN], lst[MAXN], dp[MAXN];

int main() {
    n = readint(); l = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j * j <= a[i]; j++) {
            if(a[i] % j == 0) {
                if(j >= l) dp[i] = std::max(dp[i], dp[lst[j]] + 1);
                if(a[i] / j >= l) dp[i] = std::max(dp[i], dp[lst[a[i] / j]] + 1);
                lst[j] = lst[a[i] / j] = i;
            }
        }
        ans = std::max(ans, dp[i]);
    }
    printf("%d", ans);
    return 0;
}