CF 264B Good Sequences(DP,数论)
文章目录
题目描述
给定一个严格上升的子序列,求其相邻元素不互质的最长上升子序列长度
$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;
}