CF-1028-C. Gellyfish and Flaming Peony（通过gcd让数组所有数字相同）

思路讲解

AC代码

https://codeforces.com/contest/2115/submission/322474384

源代码

// Problem: A. Gellyfish and Flaming Peony
// Contest: Codeforces - Codeforces Round 1028 (Div. 1)
// URL: https://codeforces.com/contest/2115/problem/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
// #define getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin() \
,var.end())-var.begin());} while (0)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef int ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(5e3)+10,INF=static_cast<ll>(1e9)+9;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
ll dp[MAXN];
ll mnGcd=0,las=0;
ll Cnt[MAXN];
bool vis[MAXN];
inline ll gcd(ll a,ll b){
	if(a<b) swap(a,b);
	while(b){
		a%=b;
		swap(a,b);
	}
	return a;
}
ll dfs(ll x,ll idx){		// 递归函数的lambda实现稍微有点困难
	if(x==mnGcd) return 0;
	if(dp[x]) return dp[x];
	ll ret=INF;
	FOR(i,idx+1,las){
		ll lret=dfs(gcd(x,A[i]),i);
		ret=min(lret,ret);
	}
	dp[x]=ret+1;
	return dp[x];
}

inline void solve(){
	scanf("%d",&N);
	FOR(i,1,N){
		scanf("%d",&A[i]);
	}
	ll maxA=0;
	mnGcd=A[1];
	FOR(i,1,N){
		maxA=max(A[i],maxA);
		mnGcd=gcd(mnGcd,A[i]);
	}
	ll cnt=0;
	FOR(i,0,maxA) dp[i]=0,vis[i]=false,Cnt[i]=0;
	FOR(i,1,N) {if(A[i]==mnGcd) ++cnt;++Cnt[A[i]];}
	
	sort(A+1,A+1+N);
	las=unique(A+1,A+1+N)-A-1;
	dp[mnGcd]=0;
#ifdef LOCAL
    debug(mnGcd);
    debug(las);
#endif
	ll mnC=INF;
	FOR(i,1,las){
		if(A[i]==mnGcd){mnC=0;break;}
		dfs(A[i],i);
		mnC=min(dp[A[i]],mnC);
	}
#ifdef LOCAL
   FOR(i,1,maxA){if(dp[i]){debug(i);debug(dp[i]);}}
   cerr<<"\n";
#endif
	ll ans=0;
	if(cnt){
		ans=N-cnt;
	}else{
		ans=N+mnC-1;
	}
	printf("%d\n",ans);
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	scanf("%lld",&lT);
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2115/submission/322474384
*/

心路历程（WA，TLE，MLE……）