题目链接

题目描述

给定一个严格上升的子序列，求其相邻元素不互质的最长上升子序列长度

$n,a_i \le 10^5$

简要做法

$$ f_i = \max_{\gcd(a_j,a_i)>1\ ,\ j < i}{f_j} + 1 $$

暴力的 $O(n^2)$ 是显然的，考虑优化状态转移

$f_i$ 能从 $f_j$ 转移过来，当且仅当 $a_i$ 和 $a_j$ 有共同因子

记录一个数组 $g_i = \max{f_x}$，其中 $i | x$

对于每个 $a_i$，将其分解质因数，从每个因子的 $g$ 那边转移过来，即每个因子能转移到的最大的 $f$

参考代码

#include <stdio.h>
#include <algorithm>
#include <math.h>

const int N = 1e5 + 5;

int n, ans;
int a[N], b[N];
int f[N], g[N];
int cnt, prime[N];
bool isPrime[N];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1, tmp; i <= n; i++)
    {
        f[i] = 1, tmp = a[i];
        for (int j = 2; j * j <= a[i]; j++)
            if (tmp % j == 0)
            {
                f[i] = std::max(f[i], g[j] + 1);
                while (tmp % j == 0)
                    tmp /= j;
            }
        if (tmp > 1)
            f[i] = std::max(f[i], g[tmp] + 1);
        ans = std::max(ans, f[i]), tmp = a[i];
        for (int j = 2; j * j <= a[i]; j++)
            if (tmp % j == 0)
            {
                g[j] = std::max(g[j], f[i]);
                while (tmp % j == 0)
                    tmp /= j;
            }
        if (tmp > 1)
            g[tmp] = std::max(g[tmp], f[i]);
    }
    return printf("%d", ans), 0;
}