P8792题解

· · 题解

思路

若要使序列最后只剩下 1，则序列中本身一定要有 1。也就将问题转换为，找到一个长度最小的区间，使得区间 \gcd 为 1。最后的答案就是区间长度减一再加上 n-1。

因为 \gcd(a,b,c)=\gcd(\gcd(a,b),\gcd(b,c))。满足结合律，所以容易想到使用线段树维护区间 \gcd。接下来只要使用双指针把整个序列扫一遍就行啦。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct tree{
    int l,r,gcd;
}t[N<<2];
int n,a[N],ans;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void build(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].gcd=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p].gcd=__gcd(t[p<<1].gcd,t[p<<1|1].gcd);
}
int ask(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].gcd;
    }
    int mid=(t[p].l+t[p].r)>>1;
    int q=0,o=0;
    if(l<=mid)q=ask(p<<1,l,r);
    if(r>mid)o=ask(p<<1|1,l,r);
    if(!q)return o;
    if(!o)return q;
    return __gcd(o,q);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    int i=0,ans=1145141919;
    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);
    }
    cout<<ans+n-1; 
    return 0;
}