Codeforces Round 973 (Div. 2) E. Prefix GCD（n个数重排使得gcd前缀和最小 补写法）

题目

思路来源

元老群群友

题解

每一步都取最小的即可，gcd log次就变1了所以暴力就完了

代码1

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10;
int t,n,a[N];
int gcd(int x,int y){
    return !y?x:gcd(y,x%y);
}
int main(){
    sci(t);
    while(t--){
        sci(n);
        int g=0,mn=0;
        rep(i,1,n){
            sci(a[i]);
            g=gcd(g,a[i]);
        }
        ll ans=0;
        rep(i,1,n){
            if(mn==g){
                ans+=1ll*(n-i+1)*mn;
                break;
            }
            int nmn=N;
            rep(j,1,n){
                nmn=min(nmn,gcd(mn,a[j]));
            }
            mn=nmn;
            ans+=mn;
        }
        ptlle(ans);
    }
    return 0;
}

代码2（赛中写法）

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10;
int t,n,a[N],mn,p;
vector<int>fac[N],f[N];
int gcd(int x,int y){
    return !y?x:gcd(y,x%y);
}
int main(){
    sci(t);
    for(int i=1;i<N;++i){
        for(int j=i;j<N;j+=i){
            fac[j].pb(i);
        }
    }
    while(t--){
        sci(n);
        mn=N;
        rep(i,1,n){
            sci(a[i]);
            if(mn>a[i])mn=a[i],p=i;
        }
        rep(i,1,n){
            int g=gcd(a[i],mn);
            f[g].pb(i);
        }
        int now=mn;
        ll ans=mn;
        rep(i,2,n){
            if(now==1){
                ans+=n-i+1;
                break;
            }
            int mn2=now;
            for(auto &v:fac[mn]){
                if(f[v].empty())continue;
                int ng=gcd(now,v);
                if(mn2>ng)mn2=ng;
            }
            //printf("i:%d mn2:%d\n",i,mn2);
            now=mn2;
            ans+=now;
        }
        ptlle(ans);
        rep(i,1,n){
            int g=gcd(a[i],mn);
            f[g].clear();
        }
    }
    return 0;
}