P8792 [蓝桥杯 2022 国 A] 最大公约数 题解

· · 题解

题目传送门：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;
}