概要

各細胞はほかの細胞と独立に処理できるので、まず「活性値 \(a\) の細胞 1 個をすべて \(1\) にするには何回かかるか」を考えます。
すると答えは \(a\) の素因数の「取り出す順番」だけで決まり、最小は小さい素数から、最大は大きい素数から取り出せばよいです。

考察

1. 初期の各細胞は独立

ある細胞に対する操作は、その細胞から生まれた子孫の細胞にしか影響しません。
別の初期細胞から生まれた細胞とは一切干渉しないので、

• 各 \(A_i\) について必要操作回数の最小値・最大値を求める
• それらを全部足す

で全体の答えになります。

---

2. 1 個の細胞だけを見る

活性値 \(x\) の細胞に対して、素因数 \(p\) を選ぶと

• \(x\) を 1 個消す
• 代わりに \(x/p\) の細胞を \(p\) 個作る

という操作になります。

たとえば \(12\) に対して \(p=2\) を選ぶと

• \(12 \to 6,6\)

です。
さらにそれぞれの \(6\) にまた操作していきます。

---

3. 操作回数は「素因数を取り出す順番」で決まる

\(a\) の素因数を重複込みで

\[ a = q_1 q_2 \cdots q_k \]

とします。
ここで「最初に \(q_1\) を選び、次に各子細胞で \(q_2\) を選び、……」という順番で進めると、

• 1 回目の操作：最初の細胞 1 個に対して行うので \(1\) 回
• 2 回目の段階：細胞が \(q_1\) 個あるので \(q_1\) 回
• 3 回目の段階：細胞が \(q_1 q_2\) 個あるので \(q_1 q_2\) 回
• …
• 最後の段階：\(q_1 q_2 \cdots q_{k-1}\) 回

したがって総操作回数は

\[ 1 + q_1 + q_1 q_2 + \cdots + q_1 q_2 \cdots q_{k-1} \]

になります。

---

4. 最小は昇順、最大は降順

では、素因数をどの順番で並べればこの和が最小/最大になるでしょうか。

隣り合う 2 つの素因数 \(a \le b\) を考え、残りの後ろ部分を固定します。
この 2 つの順番だけを比べると、

• \(a,b\) の順に置いたとき
• \(b,a\) の順に置いたとき

の差は、実は「前に大きい数を置くと、その後ろの項すべてに効いてしまう」ため、常に

\[ (a,b) の方が (b,a) より小さい \]

となります。

もう少し式で書くと、前にある素因数の積を \(P\)、後ろ部分の寄与を \(U\) とすると、

• \(a,b\) の順：\(P(1 + a + abU)\)
• \(b,a\) の順：\(P(1 + b + abU)\)

なので差は

\[ P[(1+b+abU)-(1+a+abU)] = P(b-a) \ge 0 \]

です。
つまり 小さい素因数を前に出すほど小さくなる ので、

• 最小値：素因数を 昇順
• 最大値：素因数を 降順

に並べればよいです。

---

5. 具体例

\(a=12=2 \times 2 \times 3\) を考えます。

• 最小：\(2,2,3\) の順
  $\( 1+2+2\cdot2=1+2+4=7 \)$
• 最大：\(3,2,2\) の順
  $\( 1+3+3\cdot2=1+3+6=10 \)$

実際、

• 最小の流れ
  \(12 \to 6,6\)
  \(6,6 \to 3,3,3,3\)
  \(3,3,3,3 \to 1\) たち
  で合計 \(7\) 回

• 最大の流れ
  \(12 \to 4,4,4\)
  \(4,4,4 \to 2\) たち
  \(2\) たち \(\to 1\) たち
  で合計 \(10\) 回

となります。

---

6. 素朴な方法がだめな理由

素朴に

• 実際に細胞をシミュレーションする
• すべての選び方を探索する

と、細胞数がどんどん増えるうえ、選択肢も多くて到底間に合いません。

また、各 \(A_i\) を毎回試し割りで素因数分解すると、\(N\) が最大 \(2\times10^5\) なので重くなります。
そこで、あらかじめ 最小素因数表 (SPF) を作っておくと、高速に素因数分解できます。

アルゴリズム

1. \(M=\max(A_i)\) とする。
2. \(1\) から \(M\) までの 最小素因数 spf をエラトステネス風に前計算する。
3. 各 \(A_i\) について以下を行う。
   1. spf を使って素因数を重複込みで列挙する。
      この実装では自然に昇順で得られる。
   2. 最小値を計算する。
      昇順の素因数列を \(p_1,p_2,\dots,p_k\) とすると $\( 1 + p_1 + p_1p_2 + \cdots + p_1p_2\cdots p_{k-1} \)$ を求める。
   3. 最大値を計算する。
      同じ素因数列を逆順にして、同様に $\( 1 + q_1 + q_1q_2 + \cdots + q_1q_2\cdots q_{k-1} \)$ を求める。
4. それぞれ全 \(A_i\) 分を足して出力する。

同じ値が何度も出る場合に備えて、memo で結果を再利用しています。

計算量

• 時間計算量: \(O(M \log \log M + N \log M)\)
  ただし \(M=\max(A_i)\)
  （素因数分解 1 回あたりの回数は、割るたびに少なくとも \(2\) で割れるので高々 \(O(\log M)\)）
• 空間計算量: \(O(M + N)\)

実装のポイント

• spf[x] を使えば、x を高速に素因数分解できます。
• 素因数列から答えを作るときは、
  prod = 1 として
  • 現在の prod を答えに足す
  • prod *= p

を順に繰り返せば $\( 1,\ p_1,\ p_1p_2,\ \dots \)\( を自然に作れます。 - \)A_i=1\( のときは操作不要なので \)(0,0)$ です。 - 合計値は大きくなりうるので、他言語なら 64bit 整数が必要です。

ソースコード

import sys
from math import isqrt

def build_spf(n: int):
    spf = [0] * (n + 1)
    if n >= 2:
        for i in range(2, n + 1, 2):
            spf[i] = 2
        r = isqrt(n)
        for i in range(3, n + 1, 2):
            if spf[i] == 0:
                spf[i] = i
                if i <= r:
                    step = i << 1
                    start = i * i
                    for j in range(start, n + 1, step):
                        if spf[j] == 0:
                            spf[j] = i
    return spf

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n = data[0]
    A = data[1:1 + n]
    m = max(A) if A else 1

    spf = build_spf(m)

    memo = {1: (0, 0)}
    total_min = 0
    total_max = 0

    for a in A:
        res = memo.get(a)
        if res is None:
            x = a
            facs = []
            while x > 1:
                p = spf[x]
                facs.append(p)
                x //= p

            prod = 1
            mn = 0
            for p in facs:
                mn += prod
                prod *= p

            prod = 1
            mx = 0
            for p in reversed(facs):
                mx += prod
                prod *= p

            res = (mn, mx)
            memo[a] = res

        total_min += res[0]
        total_max += res[1]

    print(total_min, total_max)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。