链接
Number
思路
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5+10; const int mod = 1e9+7; int a[maxn]; int cnt[maxn]; queue<int> q; map<int,int> dis[maxn]; //表示第i个数开方或者平方所到达的数所需的最小次数 int main(void){ int n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++){ dis[i][a[i]] = 1; cnt[a[i]]++; q.push(a[i]); while(!q.empty()){ ll u = q.front(); ll v = u*u; q.pop(); if(dis[i][v]==0&&v<=1e5){ dis[i][v] = dis[i][u]+1; cnt[v]++; q.push(v); } v = (int)sqrt(u); if(dis[i][v]==0){ dis[i][v] = dis[i][u]+1; cnt[v]++; if(v!=1) q.push(v); } } } ll ans = 0x3f3f3f3f; for(int i = 1; i <= 1e5; i++){ if(cnt[i]==n){ ll res = 0; for(int j = 1; j <= n; j++){ res += (dis[j][i]-1); } ans = min(ans,res); } } cout<<ans<<endl; return 0; }