【题解】最大公约数

2024-02-21 11:37:58

题面

题目背景

寻求最大公约数是人民*的真谛。

题目描述

小 L 极其喜爱 gcd ⁡ \gcd gcd。

有一天，小 Z ：小 L，问你个题。

小 Z：给出一个长度为 n n n 的序列 a a a 和一个整数 k k k ，把这个序列划分成连续的 k k k 段，每一段不能为空。

小 L：等等， gcd ⁡ \gcd gcd 去哪里了。

小 Z：别急嘛，我们设 b i b_i bi 表示第 i i i 段的最大值，请问怎么划分该序列使得 gcd ⁡ ( b 1 , b 2 , . . . , b k ) \gcd(b_1,b_2,...,b_k) gcd(b1,b2,...,bk) 的值最大。

小 L 沉思了一会，发现自己不会做，彻底地自闭了，于是他又向你来求助了，请你帮帮他。

输入格式

输入文件名为 gcd.in。

输入文件第一行包含两个整数 n n n , k k k，表示序列的长度和需要划分的段数。

接下来第二行包含 n n n 个整数，表示这个序列。

输出格式

输出文件名为 gcd.out。

输出文件包含一个整数，表示你的答案。

样例

样例输入 1

5 3
1 3 2 9 6

样例输出 1

样例解释 1

最优的划分可能有多种，这里给出一种最优的划分，将序列分成 [ 1 , 3 ] [1,3] [1,3] , [ 2 , 9 ] [2,9] [2,9] , [ 6 ] [6] [6] 三段，其中 b 1 = 3 b_1=3 b1=3 , b 2 = 9 b_2=9 b2=9 , b 3 = 6 b_3=6 b3=6，所以答案为 gcd ⁡ ( 3 , 9 , 6 ) = 3 \gcd(3,9,6)=3 gcd(3,9,6)=3 。

数据规模与约定

对于 100 % 100\% 100% 的数据， 1 ⩽ k ⩽ n ⩽ 1 0 3 1\leqslant k\leqslant n\leqslant 10^3 1⩽k⩽n⩽103 , 1 ⩽ k ⩽ 5 × 1 0 2 1\leqslant k \leqslant 5\times 10^2 1⩽k⩽5×102 , 1 ⩽ a i ⩽ 1 0 6 1\leqslant a_i\leqslant 10^6 1⩽ai⩽106。

Solution

~~出题人米巴米巴吃多了，一上来就给一道数论?~~

彻底自闭的是我才对吧。。。【欲哭无泪.gif】

看起来。。。貌似是道。。。DP？[凭感觉做题晚期患者再次上线]

每个分段的最大值里面，一定会有整个序列的最大值，也就是说，最终求到的 gcd ⁡ \gcd gcd ，一定是最大值的因数。

因为分组未知的情况下，只能求得整个序列的最大值，我们以此为突破口。

设最大值为 m x mx mx .

枚举 m x mx mx 的每个因数为最大公约数的情况， d i v i i divi_i divii 表示 m x mx mx 从 1 1 1 开始的第 i i i 个因数。

那么，我们已经（其实是我）想象到了这可能是一道DP，那么状态呢？

对于 divi[i] , dp[j] 表示前 j 个数可以分成的最大段数，并且每一段的最大值都是 divi[i] 的倍数

状态转移方程的柿子呢？

设 mxx 为 a[k]~a[j](k<=j) 的最大值
如果 divi[i] 整除 mxx:
	dp[j]=max(dp[j],dp[k-1]+1);

为什么？

既然 m x x mxx mxx 是当前的最大值，并且 m x x mxx mxx 也是 d i v i i divi_i divii 的倍数，那么 m x x mxx mxx 就可以作为当前分段的最大值。

而我们要保证可以分的段数最大，我们想， m x x mxx mxx 表示的是 a k a_k ak ~ a j a_j aj 的最大值，那么，我们就将 a k a_k ak ~ a j a_j aj 分为一段不就行了？

而分到这里最大的段数就是分到 a k − 1 a_{k-1} ak−1 时的最大段数加上当前段的 1 1 1 。

如果对于 d i v i [ i ] divi[i] divi[i]， d p n dp_n dpn 可以分的段数 ⩾ k \geqslant k ⩾k，因为 d i v i i divi_i divii 是从小到大排列的，最新的一定是最大的，我们直接更新答案。

初始化时，因为要求最大值，初始化成 − 0 x 3 f 3 f 3 f 3 f -0x3f3f3f3f −0x3f3f3f3f ， d p 0 = 0 dp_0=0 dp0=0 。

Code

#include<cstdio>
#include<cstring>
const int maxn=1e3+5;
int a[maxn];
int dp[maxn];
int divi[maxn];
int n,k,mx,tot,ans;
int max(int x,int y){
	return x>y?x:y;
}
void read(int&x){
	x=0;
	bool f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=x*10+(ch&15);
		ch=getchar();
	}
	if(f)x=-x;
	return;
}
int main(){
	read(n);read(k);
	for(int i=1;i<=n;++i){
		read(a[i]);
		mx=max(mx,a[i]);
	}
	for(int i=1;i<=mx;++i){
		if(mx%i==0)
			divi[++tot]=i;
	}
	for(int i=1;i<=tot;++i){
		memset(dp,-0x3f3f3f3f,sizeof(dp));
		dp[0]=0;
		for(int j=1;j<=n;++j){
			int mxx=-0x3f3f3f3f;
			for(int k=j;k;--k){
				mxx=max(mxx,a[k]);
				if(mxx%divi[i]==0)
					dp[j]=max(dp[j],dp[k-1]+1);
			}
		}
		if(dp[n]>=k)ans=divi[i];
	}
	printf("%d",ans);
	return 0;
}

end.

码农公寓

题面