概要

この問題は、与えられた活性値 \(A_i\) を素因数分解する過程で発生する「操作回数」を、分解する素数の順番を工夫することで最小化・最大化する問題です。 各操作は「活性値 \(x\) を \(p\) 個の \(x/p\) に分ける」というルールに基づき、最終的にすべての細胞の活性値が \(1\) になるまで繰り返します。

考察

操作の構造を理解する

活性値 \(x\) の細胞に対して素数 \(p\) を選んで操作を行うと、活性値 \(x/p\) の細胞が \(p\) 個生成されます。 この \(p\) 個の細胞それぞれに対して、再び活性値が \(1\) になるまで操作を繰り返します。 活性値 \(x\) をすべて \(1\) にするのに必要な操作回数を \(f(x)\) とすると、以下の再帰式が成り立ちます。

\[f(x) = 1 + p \times f(x/p)\]

（ただし、活性値が \(1\) のときは操作できないので \(f(1) = 0\) です）

具体例で考える

例えば、活性値 \(12\) の細胞を考えます。\(12\) の素因数は \(\{2, 2, 3\}\) です。

1. 小さい素数から選ぶ場合 (\(p=2 \to 2 \to 3\))

   • \(f(12) = 1 + 2 \times f(6)\)
   • \(f(6) = 1 + 2 \times f(3)\)
   • \(f(3) = 1 + 3 \times f(1) = 1 + 3 \times 0 = 1\)
   • 代入していくと：\(f(12) = 1 + 2 \times (1 + 2 \times 1) = 1 + 2 \times 3 = 7\)

2. 大きい素数から選ぶ場合 (\(p=3 \to 2 \to 2\))

   • \(f(12) = 1 + 3 \times f(4)\)
   • \(f(4) = 1 + 2 \times f(2)\)
   • \(f(2) = 1 + 2 \times f(1) = 1\)
   • 代入していくと：\(f(12) = 1 + 3 \times (1 + 2 \times 1) = 1 + 3 \times 3 = 10\)

この例からわかるように、「小さい素数から割っていくと操作回数が少なくなり、大きい素数から割っていくと操作回数が多くなる」という性質があります。 数式を展開すると、\(x = p_1 p_2 \dots p_k\) と分解したとき、操作回数は \(1 + p_1 + p_1 p_2 + p_1 p_2 p_3 + \dots + (p_1 p_2 \dots p_{k-1})\) となるため、前の方に小さい数字が来るほど全体の和は小さくなります。

アルゴリズム

各 \(A_i\) に対して独立に計算し、その総和を求めます。\(A_i\) の最大値 \(M = 10^6\) であるため、各数値について高速に最小・最大操作回数を求める必要があります。

1. 素因数の事前計算 (エラトステネスの篩の応用)

   • 各数値 \(x\) について、その数値を割り切る「最小の素数 (SPF)」と「最大の素数 (LPF)」をあらかじめ求めておきます。
   • これにより、各数値の素因数分解を高速に行えるようになります。

2. 動的計画法 (DP)

   • \(f_{min}[x]\) : 活性値 \(x\) をすべて \(1\) にする最小操作回数
   • \(f_{max}[x]\) : 活性値 \(x\) をすべて \(1\) にする最大操作回数
   • 以下の遷移式で \(x=2\) から \(M\) まで計算します。
     • \(f_{min}[x] = 1 + SPF[x] \times f_{min}[x / SPF[x]]\)
     • \(f_{max}[x] = 1 + LPF[x] \times f_{max}[x / LPF[x]]\)

3. 集計

   • 入力された各 \(A_i\) について \(f_{min}[A_i]\) と \(f_{max}[A_i]\) を足し合わせます。

計算量

• 時間計算量: \(O(M \log \log M + N)\)

  • 篩による素因数の事前計算に \(O(M \log \log M)\)（LPFの更新を工夫すれば \(O(M)\) も可能）。
  • DPによるテーブル作成に \(O(M)\)。
  • \(N\) 個の入力に対する答えの集計に \(O(N)\)。
  • \(M=10^6, N=2 \times 10^5\) であれば、制限時間内に十分間に合います。

• 空間計算量: \(O(M)\)

  • SPF, LPF, \(f_{min}, f_{max}\) の各テーブルを保持するために \(O(M)\) のメモリを使用します。

実装のポイント

• Pythonでは、大量の数値計算を高速化するために sys.stdin.read().split() で一括入力を行い、ループを効率的に回す工夫が必要です。

• 最大素因数 (LPF) を求める際、エラトステネスの篩の要領で「各素数の倍数に対して、その素数で上書きしていく」処理を行うと、最終的に各数値にはその数値を割り切る最大の素数が残ります。

• Pythonのリストのスライス代入（lpf[i*2 : M+1 : i] = [i] * num）を利用すると、ループを回すよりも高速にテーブルを更新できます。

  ソースコード

import sys

def solve():
    # Fast I/O: Read all input at once
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: number of initial cells
    # A: initial activity values
    N = int(data[0])
    A = map(int, data[1:])
    
    # M: maximum possible activity value
    M = 1000000
    
    # SPF: Smallest Prime Factor
    spf = list(range(M + 1))
    for i in range(2, int(M**0.5) + 1):
        if spf[i] == i:
            for j in range(i * i, M + 1, i):
                if spf[j] == j:
                    spf[j] = i
    
    # LPF: Largest Prime Factor
    lpf = list(range(M + 1))
    for i in range(2, M + 1):
        if lpf[i] == i:
            # For each prime i, update its multiples. 
            # The largest prime factor of a number will be the last one to update it.
            if i * 2 <= M:
                # Use slice assignment for optimized speed in Python
                num = (M - i) // i
                lpf[i*2 : M+1 : i] = [i] * num
    
    # DP to precompute the minimum and maximum operations for each activity value.
    # f_min[x] = 1 + p_min * f_min[x / p_min]
    # f_max[x] = 1 + p_max * f_max[x / p_max]
    # To minimize total operations, we choose the smallest prime factor first.
    # To maximize total operations, we choose the largest prime factor first.
    f_min = [0] * (M + 1)
    f_max = [0] * (M + 1)
    for x in range(2, M + 1):
        s = spf[x]
        f_min[x] = 1 + s * f_min[x // s]
        l = lpf[x]
        f_max[x] = 1 + l * f_max[x // l]
    
    # Calculate the total operations for all initial cells
    total_min = 0
    total_max = 0
    for a in A:
        total_min += f_min[a]
        total_max += f_max[a]
        
    # Output the results separated by a space
    sys.stdout.write(f"{total_min} {total_max}\n")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。