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

Aiopr_2378 · 2022-11-21 13:23:00 · 题解

题目大意

给定 n 个正整数，每次可以取两个相邻的数的最大公因数并替换掉其中一个数，求最少多少次操作之后可以使整个数组变为 1。

解题思路

考虑只有互质的多个数在一起时，他们的 \gcd=1。也就是说，最开始变为 1 的那个数，一定是由与其相邻的多个数互质得出的。进而推出：我们只要有一个 1，就可以用最少的步骤使其他的数全变为 1。

所以我们考虑最少多少个相邻的数取 \gcd 的时候值为 1。最普遍的，我们可以枚举左右端点 l 和 r，通过 O(n^2) 的复杂度可以求出答案。

进一步考虑优化：

我们发现，若存在 l,r 两端点，使得 \gcd\{a_l,a_{l+1},\cdots,a_r\}=1，则必然存在 \gcd\{a_{l-1},a_l,\cdots,a_r\}=1。进而可以推广，得知我们由大范围可以逐渐缩小范围，可以使用双指针的方法实现降维。

另外，为了更快的求出区间的 \gcd，我们可以使用线段树、树状数组、稀疏表等方法实现 O(\log n+\log a_i) 的复杂度解决区间 \gcd 的问题，因为作者比较懒，使用了稀疏表的方法解决（主要是码量小）。

注意常数优化/kk

参考代码

#include<iostream>
using namespace std;
#define MAXN 100005
int n,lg[MAXN],f[30][MAXN];
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int query(int l,int r){
    int tmp=lg[r-l+1];
    return gcd(f[tmp][l],f[tmp][r-(1<<tmp)+1]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>f[0][i];
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int j=1;j<=lg[n];j++){
        for(int i=1;i<=n;i++){
            f[j][i]=gcd(f[j-1][i],f[j-1][i+(1<<(j-1))]);
        }
    }
    if(query(1,n)>1) return puts("-1"),0;
    int l=1,r=1,ans=0x3f3f3f3f;
    for(;r<=n;r++){
        while(l<r&&query(l+1,r)==1) l++;
        if(query(l,r)==1) ans=min(ans,r-l);
    }
    cout<<n+ans-1;
    return 0;
}