囧仙 的博客

囧仙 的博客

题解 CF891A 【Pride】

posted on 2020-10-04 09:11:02 | under 题解 |

题目大意

给定 $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;
}