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

· · 题解

这里给出一个不一样的做法

(时间复杂度玄学，希望大佬帮忙分析一下 QAQ )

题外话(模拟赛上的题，但是脑子抽了没写出正解，就写了一个优雅的暴力，跑到了最优解 page 1 )

顺带一提(因为模拟赛上采用思路一的暴力过不去，但 lg 可以过，什么鬼数据，，所以跟大家分享一下思路二这种做法)

传送门

双倍经验(思路一的代码不加优化可以过，水蓝)

题意分析

这道题的操作其实就是求两个数的 \gcd 并替换其中一个数。我们知道如果要使整个数列全部变为 1 的话，那么我们在进行若干次(小于 n 次)操作后，必定会出现 1。那么我们用这个1去和其它不是 1 的数求 \gcd，就能将整个序列变成 1

思路(还有一种带log的做法其它大佬讲了我就不讲了)

一 考虑暴力(其实只要在原暴力上加个优化就过了)

我们知道\gcd(a,b,c)=\gcd(\gcd(a,b),\gcd(b,c))，它满足结合律

证明

那么我们对于每一个 a[i]，先用它和 a[i+1] 取 \gcd (记为 x)，再用 x 与 a[i+2] 求 \gcd (记为 x )，以此类推，一直到 a[k] ，那么此时的 x 就是 \gcd(a[i],a[i+1],......,a[k]),而我们假设取到 a[k] 时 x 为 1，那么相当于我们进行了 k-i 次操作后得到了 1

以上面的思路，我们枚举 i，ans=n-1(还有 n-1 个不为 1)+ \min(k-i)，时间复杂度为 O(n^{2})

当然，我们要特判，如果原序列中有了 res 个 1，那么 ans=n-res(将不是 1 的 n-res 个原序列中的数和它相邻的 1 进行操作)

期望得分 100 (不加优化 80)(而且为哈其它题解都没有这种写法啊啊啊)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+100;
int n,a[N],res;
main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i],res+=(a[i]==1?1:0);
    if (res){
        cout<<n-res;
        return 0;
    }
    int step=1e9;
    for (int i=1;i<n;i++)
    {
        int x=a[i];
        for (int j=i+1;j<=n;j++)
        {
            x=__gcd(x,a[j]);//求gcd的自带函数 
                  if(j-i>step) break;//优化
            if(x==1)
            {
                step=j-i;
                break;
            }

        }
    }
    if (step==1e9) cout<<-1;
    else cout<<n-1+step;
    return 0;
}

二 还是考虑暴力

我们考虑对思路一进行优化

我们可以发现，思路一中造成超时的主要原因是因为我们没法保证每次得出的 step 是最优解，因此我们要跑满 n^2 次(其实不算跑满，因为有个优化)

但是如果我们能保证第一次得出的答案即为最优，那么嘿嘿嘿(这里说一下，其实多数题目可以这样思考，因为出题人是知道朴素暴力怎么卡的，所以他肯定会卡，而我们只要绕开这点，就可以让出题人的卡暴力成为我们 AC 的依据)

好了好了，进入正题

我们先借用一篇巨佬的 blog 介绍一下 \gcd 的求法

here

我建议大家使用第四种，因为可以处理 a, b 为 0 的情况并且速度较快(当然用 c++ 自带的 \gcd 函数也可以 AC 本题)

紧接着我们回忆一下思路一，其中的 \gcd 的结合律也许可以给我们一点启发。我们知道，若有 n 个数，那么我们取其中至少包含 2 个数的连续区间求这个区间所有数的 \gcd，

一共可以得出 \frac{n\times(n-1)}{2} 个结果(长度为 2 的有 n-1 个，为 3 的有 n-2 个，以此类推)

那我们要求的不就是一个连续区间使一个区间所有数的 \gcd 为 1 的最小长度吗

那我们只要从区间长度入手，每次枚举出长度为 2,3,......,n 的连续区间，再来统计它们的 \gcd 是否为 1，就可以保证我们第一次找出的答案即为最优

对一些可能的疑惑的解答(为什么只找一个)：当然，我们只需要一个连续区间的 \gcd 为 1 就好了，因为我们只需要一个 1 就能使其它数都变成 1 (如果找两个区间的话那么操作次数会 -1 再 + 区间长度，-1 是因为多变了一个 1，+ 区间长度是因为要额外进行这么多次操作)

我们接着思考，长度为 3 的连续区间的 \gcd 可以由两个长度为 2 的连续区间的 \gcd 得到，以此类推，下面给出一张图便于理解

上图以 n=6 举例，a 为原序列，b 为相邻两个 a 数组中的数的 \gcd，c 为相邻两个 b 数组中的数的 \gcd (即 a 中相邻三个数的 \gcd )，以此类推，最后我们迭代的层数即为操作几次后可以得出一个 1。

具体实现：我们新建一个 b 数组，初始有 tot=n 个数，每一次迭代使 b[i]=\gcd(b[i],b[i+1]),检查此时 b[i] 是否为 1，若为 1 就 break，输出 n-1+ 迭代次数 即为答案(不难看出，tot 每次会减 1，若 tot=0 则说明没有解)

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
//#define int long long
#define re register
using namespace std;
const int N=1e5+110;
int n,a[N],num,res;
bool f;
int b[N],tot,k;
inline int read()
{
    int ress=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) ress=(ress<<3)+(ress<<1)+c-'0',c=getchar();
    return ress;
}
inline int gcd_(int x2,int y2)
{
    int x=max(x2,y2),y=min(x2,y2);
    if(y) while((x%=y)&&(y%=x)) ;
    return x+y;
}
signed main()
{
    n=read();
    for(re int i=1;i<=n;++i) 
    {
        b[i]=a[i]=read();
        if(a[i]==1) ++num;
    }
    if(num) {printf("%d",n-num);return 0;}//特判，前面思路一讲过
    tot=n;
    if(n==1) return printf("-1"),0;
    int gg=gcd_(a[1],a[2]);
    for(re int i=3;i<=n;++i)gg=gcd_(gg,a[i]);
  //这个特判可以加可以不加，因为模拟赛的时候后面几个大的数据点是-1，如果最后判断的话可以卡成n^2的
    if(gg>1) return printf("-1"),0;
    while(!f&&k<n)
    {
        ++k;//迭代层数
        --tot;//当前b数组中数的个数
        for(re int i=1;i<=tot;++i)
        {
            b[i]=gcd_(b[i],b[i+1]);
            if(b[i]==1)
            {
                f=1;
                break ;
            }
        }
        if(f) break ;
    }
    if(!f) printf("-1");
    else printf("%d",n-1+k);
    return 0;
}

至此，本题解决，在 O2 的加持下可以只跑 104ms

最后，我再来说一个小优化思路(可以在迭代 b 数组时判断，若 b[l] 到 b[r] 之间全部相等，r-l+1>=2，那么我们可以只保留 b[l] 和 b[r]，因为两个相同的数的 \gcd 永远是它们本身，可以通过链表实现)那么为什么加这个优化呢，因为这种做法被卡的话，通过此优化可以完美避免被卡掉(自行思考为什么呢)，有兴趣的同学可以自己去试试