自动搬运

查看原文

来自洛谷，原作者为

	gesong1234 花有重开日，人有重开时||RP+=INF

搬运于2025-08-24 22:42:31，当前版本为作者最后更新于2022-11-12 18:07:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门：P8792 [蓝桥杯 2022 国 A] 最大公约数。

思路

其实，这道题就是枚举，只需要枚举从哪个端点开始，如果合成了 $1$，就更新最大值，具体看代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1234567],cnt;
main(){
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i],cnt+=(a[i]==1?1:0);
	if (cnt){//特判，如果有1了，就不用枚举了。
		cout <<n-cnt;
		return 0;
	}
	int ans=1e9;
	for (int i=1;i<n;i++){//枚举开始端点
		int x=a[i],sum=0;
		for (int j=i+1;j<=n;j++){
			sum++;
			x=__gcd(x,a[j]);
			if (x==1){//成功了
				ans=min(ans,sum);
				break;
			}
		}
	}
	if (ans==1e9) cout <<-1;//不合法
	else cout <<n+ans-1;
    return 0;
}

结果TLE了，我们要想想优化。

优化

我们发现，在枚举的时候，一直用 $O(n^2)$ 的算法，如果线段树，就能减少时间，代码：

#include<bits/stdc++.h>
#define int long long
#define lc 2*k
#define rc 2*k+1
using namespace std;
int n,a[1234567],cnt;
struct nord{
	int l,r,mx;
}t[1234567];
void build(int k,int l,int r){//建树
	t[k].l=l,t[k].r=r;
	if (l==r){
		t[k].mx=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(lc,l,mid);
	build(rc,mid+1,r);
	t[k].mx=__gcd(t[lc].mx,t[rc].mx);
}
int ask(int k,int l,int r){//求区间gcd
	if (l<=t[k].l&&r>=t[k].r) return t[k].mx;
	int ans=0;
	int mid=(t[k].l+t[k].r)/2;
	if (l<=mid) ans=__gcd(ans,ask(lc,l,r));
	if (r>mid) ans=__gcd(ans,ask(rc,l,r));
	return ans;
}
main(){
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i],cnt+=(a[i]==1?1:0);
	build(1,1,n);
	if (cnt){//特殊情况
		cout <<n-cnt;
		return 0;
	}
	int ans=1e9;
	int i=1;
	for (int j=1;j<=n;j++){//枚举
		while (i<j&&ask(1,i+1,j)==1) i++;//一直往前走
		if (ask(1,i,j)==1) ans=min(ans,j-i);//成功了
	}
	if (ans==1e9) cout <<-1;//不合法
	else cout <<n+ans-1;
    return 0;
}