题解 CF891A 【Pride】

## 题目大意 给定 $n$ 个正整数。每次选择两个相邻的数 $a,b$ ，使其中一个变成 $\gcd(a,b)$ 。求使所有正整数变成 $1$ 的最少步骤。 ## 题解 显然， $\gcd(1,x)=1$ 。于是，只要我们已经获得了一个 $1$ ，就能用它向两边扩展，使得任何数字都能变成 $1$ 。显然，这种贪心是最优的。 显然，假设数列中有 $c$ 个 $1$ ，我们只需要操作 $n-c$ 次就行了。 考虑如何获得一个 $1$ 。显然，若一段区间的 $\gcd$ 不为 $1$ ，那么这个区间中无论如何都不能处理出 $1$ 。因此，我们可以合并一个区间获得 $1$ ，当且仅当这个区间的 $\gcd$ 为 $1$ 。只要求出最小的这样的区间长度 $l$ 。 合并这样的区间需要 $l-1$ 次操作。合并后恰好得到一个 $1$ ，于是还需要花费 $n-1$ 次操作。 于是，该题的答案就很显然了。 $$ans=\begin{cases}n-c & c\neq 0 \cr l+n-2 & c=0 \cr -1 & l \text{不存在}\end{cases}$$ 至于寻找最小的 $l$ ，由于 $n\le 2000$ ，于是我们可以暴力计算。这样的复杂度是 $\mathcal O(n^2\log v)$ 。当然，还有一个小优化。当我们固定区间的右端点时，向左移动左端点， $\gcd$ 值只会变化最多 $30$ 次（因为一个数的质因子个数不超过 $30$ ，而每次取 $\gcd$ 要么不变，要么至少删除一个质因子）。而 $\gcd(a,b)=a$ 等价于 $a | b$ ，可以直接判断；否则暴力取 $\gcd(a,b)$ 。这样的复杂度是 $\mathcal O(n^2+n \log v)$ 。 ## 参考代码 ``` #include<bits/stdc++.h> #define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i) #define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i) using namespace std; typedef long long i64; const int INF =2147483647; const int MAXN =2e3+3; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } int n,A[MAXN],c,t=INF; int main(){ n=qread(); up(1,n,i) A[i]=qread(); up(1,n,i){ int s=A[i]; dn(i,1,j){ if(A[j]%s==0) continue; s=__gcd(s,A[j]); if(s==1){t=min(t,i-j+1);break;} } if(A[i]==1) ++c; } if(c) printf("%d\n",n-c); else if(t!=INF) printf("%d\n",n+t-2); else printf("-1"); return 0; } ```