ひとつの細胞の分解は他の細胞の分解に影響を及ぼさないので、操作の最小回数は次の方策によって達成できます。

• 細胞に \(1\) つずつ着目し、各細胞を最小の手数で活性値 \(1\) の細胞に分解する。

最大も同様に、次の方策で達成できます。

• 細胞に \(1\) つずつ着目し、各細胞を最大の手数で活性値 \(1\) の細胞に分解する。

\(A_i \le 10^6\) に着目しつつ、次の値を \(1 \le i \le 10^6\) について全て予計算しておくことを考えます。

• \(low[i] = \{\) 活性値 \(i\) の細胞を活性値 \(1\) まで分解するための最小の手数 \(\}\)
• \(high[i] = \{\) 活性値 \(i\) の細胞を活性値 \(1\) まで分解するための最大の手数 \(\}\)

\(low,high\) をそれぞれ 動的計画法(DP) で計算することを考えます。

\(low[1]=high[1]=0\) から始めます。

\(low[i]\) を求めるためには、全ての \(i\) を割り切る素数 \(p\) について以下の値の最小値を取ればよいです。

• \(low[i/p] \times p+1\)
  • \(1\) 手かけると活性値 \(i/p\) の細胞が \(p\) 個生まれ、それらを最小手数で分解すべきだからです。

これは、 \(i\) の昇順に計算していくことができます。最大値についても同様です。

\(i\) を割り切る素数の列挙は、エラトステネスのふるいの要領で \(1 \le i \le 10^6\) の範囲で全てまとめて \(O(A_i \log \log A_i)\) で行うことができます。詳細は実装例も参考にしてください。

あとは、与えられた \(A_i\) ごとに最小値・最大値をそれぞれ足し合わせることでこの問題に正解できます。

時間計算量は \(O(A_i \log \log A_i + N)\) です。

メモ: ちゃんと考察すると DP が不要になります。
GPT 5.4 High を参照してください。これにρ法などを組み合わせることでより大きな \(A_i\) に対してこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll MXM=1000005;

int main(){
  vector<vector<ll>> pdiv(MXM);
  for(ll i=2;i<MXM;i++){
    if(!pdiv[i].empty()){continue;}
    for(ll j=i;j<MXM;j+=i){pdiv[j].push_back(i);}
  }
  vector<ll> dp_low(MXM,1e9);
  vector<ll> dp_high(MXM,0);
  dp_low[1]=0;
  dp_high[1]=0;
  for(ll i=2;i<MXM;i++){
    for(auto &nx : pdiv[i]){
      ll tg=(i/nx);
      dp_low[i]=min(dp_low[i],dp_low[tg]*nx+1);
      dp_high[i]=max(dp_high[i],dp_high[tg]*nx+1);
    }
  }

  ll N;
  cin >> N;
  ll low=0,high=0;
  vector<ll> A(N);
  for(auto &nx : A){
    cin >> nx;
    low+=dp_low[nx];
    high+=dp_high[nx];
  }
  cout << low << " " << high << "\n";
  return 0;
}