概要

細胞を分裂させる操作を繰り返し、すべての活性値を \(1\) にするまでの操作回数の最小値と最大値を求める問題です。各操作では活性値 \(x\) の細胞を素因数 \(p\) で分割し、活性値 \(x/p\) の細胞 \(p\) 個に置き換えます。

考察

操作の本質を理解する

活性値 \(x\) の細胞に対して素因数 \(p\) を選ぶと、その細胞は消えて活性値 \(x/p\) の細胞が \(p\) 個生まれます。この \(p\) 個の細胞それぞれに対してさらに操作が必要です。

具体例: \(x = 12 = 2^2 \times 3\) の場合

• 素数 \(2\) を選ぶ: 活性値 \(6\) の細胞が \(2\) 個できる → 各々をさらに処理
• 素数 \(3\) を選ぶ: 活性値 \(4\) の細胞が \(3\) 個できる → 各々をさらに処理

再帰的な定式化

\(f(x)\) を「活性値 \(x\) の細胞 1 個をすべて活性値 \(1\) にするのに必要な操作回数」とすると：

• \(f(1) = 0\)（操作不要）
• \(f(x) = \text{opt}_{p | x, p \text{ は素数}} \left(1 + p \cdot f(x/p)\right)\)

ここで \(\text{opt}\) は、最小値を求めるときは \(\min\)、最大値を求めるときは \(\max\) です。

なぜこうなるか: 1回の操作（コスト \(1\)）で \(p\) 個の活性値 \(x/p\) の細胞が生まれ、それぞれ独立に \(f(x/p)\) 回の操作が必要だからです。\(p\) 個の細胞は同じ活性値なので、合計 \(p \cdot f(x/p)\) 回の追加操作がかかります。

素朴にやるとどうなるか

\(A_i \leq 10^6\) なので、\(f(x)\) の引数として現れうる値は \(10^6\) 以下の正整数に限られます（\(x/p\) は必ず \(x\) の約数）。メモ化すれば同じ値を再計算せずに済みます。

アルゴリズム

1. 最小素因数（SPF）テーブルの構築: エラトステネスの篩の要領で、\(10^6\) 以下の各整数の最小素因数を前計算する。これにより任意の数の素因数分解が高速にできる。

2. 再帰 + メモ化で \(f_{\min}(x)\) と \(f_{\max}(x)\) を計算:

   • \(x\) の異なる素因数をすべて列挙（SPFテーブルを使って \(O(\log x)\)）
   • 各素因数 \(p\) に対して \(1 + p \cdot f(x/p)\) を計算
   • 最小版では最小値、最大版では最大値を取る

3. 答えの集計: 各 \(A_i\) に対して \(f_{\min}(A_i)\) と \(f_{\max}(A_i)\) を計算し、全細胞について合計する。

具体例での確認

\(x = 8 = 2^3\): - \(f_{\min}(8)\): 素因数は \(2\) のみ → \(1 + 2 \cdot f(4) = 1 + 2(1 + 2 \cdot f(2)) = 1 + 2(1 + 2 \cdot 1) = 1 + 6 = 7\) - つまり \(8 \to 4,4 \to 2,2,2,2 \to 1,1,1,1,1,1,1,1\) で \(1+2+4=7\) 回

計算量

• 時間計算量: \(O(M \log \log M + N)\)（\(M = 10^6\)、SPF構築に \(O(M \log \log M)\)、メモ化により各値は高々1回計算）
• 空間計算量: \(O(M)\)（SPFテーブルとメモ化キャッシュ）

実装のポイント

• SPF（Smallest Prime Factor）テーブルを使うと、素因数分解が割り算を繰り返すだけで \(O(\log x)\) でできる。

• lru_cache によるメモ化で、同じ引数の再計算を防ぐ。\(x/p\) は \(x\) の約数なので、引数の種類は \(10^6\) 以下の約数の集合に限られ、十分高速。

• 素因数を列挙する際、同じ素因数を重複して試さないように seen 集合で管理する（例: \(12 = 2^2 \times 3\) で \(2\) を2回試さない）。

  ソースコード

import sys
from functools import lru_cache

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    A = [int(input_data[i+1]) for i in range(N)]
    
    max_val = 10**6 + 1
    spf = list(range(max_val))
    for i in range(2, int(max_val**0.5)+1):
        if spf[i] == i:
            for j in range(i*i, max_val, i):
                if spf[j] == j:
                    spf[j] = i

    @lru_cache(maxsize=None)
    def f_min(x):
        if x == 1: return 0
        p = spf[x]
        # try all distinct primes, pick one minimizing
        best = float('inf')
        temp = x
        seen = set()
        while temp > 1:
            pp = spf[temp]
            if pp not in seen:
                seen.add(pp)
                best = min(best, 1 + pp * f_min(x // pp))
            while temp % pp == 0:
                temp //= pp
        return best

    @lru_cache(maxsize=None)
    def f_max(x):
        if x == 1: return 0
        temp = x
        best = 0
        seen = set()
        while temp > 1:
            pp = spf[temp]
            if pp not in seen:
                seen.add(pp)
                best = max(best, 1 + pp * f_max(x // pp))
            while temp % pp == 0:
                temp //= pp
        return best

    total_min = sum(f_min(a) for a in A)
    total_max = sum(f_max(a) for a in A)
    print(total_min, total_max)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。