Minimizing Division Operations to Equalize Numbers

You are given n positive integers \(a_1,a_2,\dots,a_n\). In one operation, you can choose a prime power \(q=p^z\) (where \(p\) is a prime and \(z\) is a positive integer) and a set of indices \(S=\{d_1,d_2,\dots,d_m\}\) such that for every index \(i\) in \(S\), \(a_{d_i}\) is divisible by \(q\). Then, for every \(i\) in \(S\), you replace \(a_{d_i}\) with \(a_{d_i} / q\>.

Determine the minimum number of operations needed to make all the numbers equal.

Explanation

Note that because you can only divide, the final equal value must be a common divisor of all input numbers. In fact, it is optimal to make all numbers equal to the greatest common divisor (gcd) of the array. Consider the prime factorization of each number. For each prime \(p\) that divides at least one of the numbers, let

[ e_i,=,\text{the exponent of }p\text{ in }a_i, \quad i=1,2,\dots,n. ]

Let (m=\min{e_1,e_2,\dots,e_n}). Then each number has an extra exponent of (d_i=e_i-m>; (d_i\ge0)) of (p) that must be removed. An allowed operation for prime (p) subtracts a positive amount (r) (i.e. divides by (p^r)) on a subset of numbers that have at least (r) extra copies remaining. Since operations for different primes are independent, the total minimum number of operations is equal to the sum over all primes of the minimal number of operations needed to remove the extra exponents for that prime.

The challenge reduces to the following sub‐problem for each prime p: Given a multiset \(\{d_1,d_2,\dots,d_n\}\) (after discarding the zero values) where each \(d_i\) is a nonnegative integer (and represents the extra exponent of \(p\)), we want to remove these extra factors using operations. In one operation you can choose a positive integer \(r\) and a subset \(S\) of indices for which the current extra exponent is at least \(r\), and subtract \(r\) from each. If we think of the operations as globally chosen “coins” \(c_1,c_2,\dots,c_k\) (each corresponding to an operation with value \(r\)), then for every extra exponent \(d\) it must be possible to represent \(d\) as a sum of some of these coins (each coin can be used at most once per number). The task is to choose the smallest number of coins (i.e. operations) such that every nonzero \(d\) in the set can be expressed as a subset sum of these coins. Note that the coins may be chosen arbitrarily (they are positive integers not exceeding the maximum \(d\) in that prime's differences) and can be applied selectively to different numbers.

For example, if the extra exponents are \(\{1,2,2,3\}\) (which comes from numbers like 4, 8, 16, 32 for a fixed prime with minimal exponent 1), then one valid set of coins is \(\{1,2\}\) because:

• \(1=1\);
• \(2=2\);
• \(3=1+2\).

Once you compute, for each prime, the minimal number of operations required, sum them up to get the answer.

Input/Output: See below.

inputFormat

The first line contains a positive integer n (\(1 \le n\le 10^5\)), the number of integers. The second line contains n positive integers \(a_1,a_2,\dots,a_n\) (each \(a_i\ge1\)).

outputFormat

Output a single integer, the minimum number of operations required to make all the numbers equal.

sample

3
1 1 1

0