Overview

Each cell can be processed independently of the others, so we first consider “how many operations does it take to reduce a single cell with activity value \(a\) entirely to \(1\)?” It turns out the answer depends only on the “order in which we extract” the prime factors of \(a\): the minimum is achieved by extracting from the smallest prime first, and the maximum by extracting from the largest prime first.

Analysis

1. The initial cells are independent

An operation on a cell only affects the descendant cells born from that cell. Cells born from different initial cells never interfere with each other, so:

• Find the minimum and maximum number of operations needed for each \(A_i\)
• Sum them all up

to get the overall answer.

---

2. Looking at a single cell

For a cell with activity value \(x\), choosing a prime factor \(p\) means:

• Remove the single cell with value \(x\)
• Create \(p\) cells with value \(x/p\) in its place

For example, choosing \(p=2\) for \(12\):

• \(12 \to 6,6\)

Then we continue operating on each of the \(6\)’s.

---

3. The number of operations is determined by the “order of extracting prime factors”

Write the prime factors of \(a\) with multiplicity as:

\[ a = q_1 q_2 \cdots q_k \]

If we proceed in the order “first choose \(q_1\), then for each child cell choose \(q_2\), …”:

• 1st stage: operate on the initial 1 cell, so \(1\) operation
• 2nd stage: there are \(q_1\) cells, so \(q_1\) operations
• 3rd stage: there are \(q_1 q_2\) cells, so \(q_1 q_2\) operations
• …
• Last stage: \(q_1 q_2 \cdots q_{k-1}\) operations

Therefore the total number of operations is:

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

---

4. Minimum with ascending order, maximum with descending order

So, in what order should we arrange the prime factors to minimize/maximize this sum?

Consider two adjacent prime factors \(a \le b\), and fix the remaining part after them. Comparing only the order of these two:

• When placed in order \(a, b\)
• When placed in order \(b, a\)

The difference arises because “placing a larger number earlier affects all subsequent terms,” and it always holds that:

\[ \text{the } (a,b) \text{ order is smaller than the } (b,a) \text{ order} \]

More precisely, letting \(P\) be the product of prime factors before them and \(U\) be the contribution from the part after them:

• Order \(a,b\): \(P(1 + a + abU)\)
• Order \(b,a\): \(P(1 + b + abU)\)

So the difference is:

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

In other words, the smaller the prime factor placed earlier, the smaller the total, so:

• Minimum: arrange prime factors in ascending order
• Maximum: arrange prime factors in descending order

---

5. Concrete example

Consider \(a=12=2 \times 2 \times 3\).

• Minimum: order \(2,2,3\) $\( 1+2+2\cdot2=1+2+4=7 \)$
• Maximum: order \(3,2,2\) $\( 1+3+3\cdot2=1+3+6=10 \)$

Indeed:

• Minimum sequence: \(12 \to 6,6\) \(6,6 \to 3,3,3,3\) \(3,3,3,3 \to 1\)’s for a total of \(7\) operations

• Maximum sequence: \(12 \to 4,4,4\) \(4,4,4 \to 2\)’s \(2\)’s \(\to 1\)’s for a total of \(10\) operations

---

6. Why a naive approach doesn’t work

If you naively:

• Simulate the actual cells
• Search through all possible choices

the number of cells grows rapidly, and there are too many choices, so it won’t finish in time.

Also, if you trial-divide each \(A_i\) for prime factorization every time, it becomes too slow since \(N\) can be up to \(2\times10^5\). Instead, by precomputing a Smallest Prime Factor (SPF) table, we can factorize quickly.

Algorithm

1. Let \(M=\max(A_i)\).
2. Precompute the smallest prime factor spf from \(1\) to \(M\) using a sieve of Eratosthenes-style approach.
3. For each \(A_i\), do the following:
   1. Use spf to enumerate prime factors with multiplicity. In this implementation, they are naturally obtained in ascending order.
   2. Compute the minimum. Given the ascending prime factor sequence \(p_1,p_2,\dots,p_k\), compute: $\( 1 + p_1 + p_1p_2 + \cdots + p_1p_2\cdots p_{k-1} \)$
   3. Compute the maximum. Reverse the same prime factor sequence, and similarly compute: $\( 1 + q_1 + q_1q_2 + \cdots + q_1q_2\cdots q_{k-1} \)$
4. Sum up the results for all \(A_i\) and output.

To handle cases where the same value appears multiple times, results are reused via memo.

Complexity

• Time complexity: \(O(M \log \log M + N \log M)\) where \(M=\max(A_i)\) (Each prime factorization takes at most \(O(\log M)\) steps since we divide by at least \(2\) each time)
• Space complexity: \(O(M + N)\)

Implementation Notes

• Using spf[x], we can quickly factorize x.
• When building the answer from the prime factor sequence, set prod = 1 and then:
  • Add the current prod to the answer
  • prod *= p

Repeating this in order naturally produces: $\( 1,\ p_1,\ p_1p_2,\ \dots \)\( - When \)A_i=1\(, no operations are needed, so the result is \)(0,0)$. - The total can become large, so in other languages, 64-bit integers are required.

Source Code

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()

---

This editorial was generated by gpt-5.4-high.