题解：CF2115A Gellyfish and Flaming Peony

· · 题解

首先一个十分显然的点是最后数组中的数都是 v=\gcd_{i=1}^na_i。

有一个比较显然的策略就是将一个数先变成 v , 然后对其他数分别进行操作，这样就全变成 v 了。

我们可以得出 a 中所有的数都是 v 的倍数，所以 (a_i,v)=v，所以只需一次操作就可以将任意数变成 v，这就能够保证这种操作是最优的。

那么我们的首要任务就是将一个数变成 v，这时就有很多方法了，比如我们可以用一种 bfs 的方法。

int a[N];
int n;
int vis[N];
int ggcd;
int que[N];
int bfs(){
    int ll=1,rr=0;
    for(int i=1;i<=n;++i){
        if(vis[a[i]]==-1){
            vis[a[i]]=0;
            que[++rr]=a[i];
            if(a[i]==ggcd) return 1;
        }
    }
    while(ll<=rr){
        int u =que[ll++];
        for(int i=1;i<=n;++i){
            int t=__gcd(a[i],u);
            if(vis[t]==-1){
                que[++rr]=t;
                vis[t]=vis[u]+1;
                if(t==ggcd) return vis[t];
            }
        }
    }
    return 0;
}

我们来看一下时间复杂度，看上去它是 O(n^2\log n) 的，但是再感性的理解一些，发现根本跑不满（尤其是本题的 a_i 很小）。于是我们就以一种很乱搞高效的方式知道将一个数字变成 v 最小要花多少步。

然后就完善一些输入输出之类的，就搞定了。

扔一坨代码