P4411 [BJWC2010] 取数游戏 题解 简单dp+桶

[BJWC2010] 取数游戏

传送门

题目描述

小 C 刚学了辗转相除法，正不亦乐乎，这小 P 又出来捣乱，给小 C 留了个 难题。 给 $N$ 个数，用 $a_1,a_2,?,a_n$来表示。现在小 P 让小 C 依次取数，第一个数可以 随意取。假使目前取得 $a_j$，下一个数取$a_k(k>j)$，则$a_k$必须满足$\gcd (a_j,a_k)\ge L$。

到底要取多少个数呢？自然是越多越好！ 不用多说，这不仅是给小 C 的难题，也是给你的难题。

输入格式

第一行包含两个数$N$ 和 $L$。 接下来一行，有 $N$ 个数用空格隔开，依次是 $a_1,a_2,?,a_n$。

输出格式

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

样例 #1

样例输入 #1

5 6 
7 16 9 24 6

样例输出 #1

3

提示

样例解释

选取 $3$个数$16,24,6$。$\gcd (16,24)=8$，$\gcd (6,24)=6$。

数据范围

30% 的数据$N\le 1000$；
100% 的数据 $N\le 50000,2\le L\le a_i\le 1000000$。

解题思路

根据题意，我们不难列出动态转移方程： $f_i=\max f_j+1(1\le j<i,\gcd (a_i,a_j)\ge L)$ 。但是，时间复杂度为 $O(n^2)$ 无法通过。

再细品，会发现 $\gcd (a_i,a_j)$ 可以用桶记录， $ton{g}_x$ 表示因数 $x$ 最近一次出现的位置，那么方程式可以写成 $f_i=\max (f_{ton{g}_x}+1)(x|a_i)$ ，则最终答案 $Ans=\max (f_i)$。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 1000000 + 5;
int N, L, a[Maxn];
int tong[Maxn], f[Maxn];
int ans;
inline void work() {
	cin >> N >> L;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j * j <= a[i]; j++) {
			if (a[i] % j == 0) {
				int tmp1 = j, tmp2 = a[i] / j;
				if (tmp1 >= L) {
					f[i] = max(f[i], f[tong[tmp1]] + 1);
					tong[tmp1] = i;
				}
				if (tmp1 != tmp2) {
					f[i] = max(f[i], f[tong[tmp2]] + 1);
					tong[tmp2] = i;
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		ans = max(ans, f[i]);
	}
	cout << ans << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}