Rating: -
Tags: -
Solve time: 28s
Verified: yes

Solution

Problem Understanding

We are given a collection of positive integers A. We must assign another positive integer B_i to every element so that every product A_i * B_i is exactly the same value. Among all possible assignments, we need the smallest possible sum of all chosen B_i. The constraints are N up to 2 * 10^5, while every A_i is at most 20.

The key restriction is the small value of each A_i. Since there are only a few possible prime factors involved, the common value of all products can be handled through prime factorization instead of through large generic algorithms. A solution that tries possible values of the common product would immediately fail because the answer can become much larger than the input values. With N = 200000, we need an algorithm close to linear time.

The main edge cases come from repeated values and numbers that contain different prime powers. For example, if the input is:

3
2 2 2

the correct output is:

The common product can be 2, giving every B_i = 1, so the sum is 3. A careless implementation might multiply all numbers and use that as the target, producing a much larger answer.

Another important case is when one number already contains a larger power of a prime:

3
2 4 8

The correct output is:

The smallest common product is 8, giving B = [4, 2, 1]. Using only the largest value seen in the array is not enough in general because the common product must be divisible by every value.

Approaches

A direct approach is to search for the smallest possible common value X such that every A_i divides X. Once X is known, each value is forced because B_i = X / A_i. This is correct because there is no freedom left after choosing the common product.

However, trying possible values of X is impossible. Even with small inputs, the least common multiple can grow quickly, and there is no useful upper bound that allows enumeration.

The observation that changes the problem is that the common product must be exactly the least common multiple of all A_i. Any valid common product is a multiple of the LCM, and choosing a larger multiple only increases every B_i. Therefore, the optimal target is the LCM itself.

Because every A_i is at most 20, we only need to keep the maximum exponent of each prime factor from 2 to 20. For example, if the numbers contain 2, 4, and 8, the LCM needs 2^3. After finding these prime exponents, we reconstruct the LCM and calculate the required sum.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Impossible to bound	O(1)	Too slow
Optimal	O(N)	O(1)	Accepted

Algorithm Walkthrough

Count the maximum power of every prime that appears in the input.

Since every value is at most 20, the only relevant primes are 2, 3, 5, 7, 11, 13, 17, and 19. Factoring each number is constant work. 2. Build the least common multiple from these maximum powers.

The LCM contains every prime factor with the largest exponent required by any input number. This is the smallest number divisible by all A_i. 3. Add LCM / A_i for every input value.

If the common product is LCM, then A_i * B_i = LCM, so B_i is uniquely determined.

Why it works: every valid solution chooses some number X divisible by every A_i. The smallest such number is the LCM. Any other valid X is a multiple of the LCM and is at least as large, which makes every value X / A_i at least as large as LCM / A_i. Therefore the LCM assignment minimizes the total sum.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    primes = [2, 3, 5, 7, 11, 13, 17, 19]
    best = [0] * len(primes)

    for x in a:
        for i, p in enumerate(primes):
            cnt = 0
            while x % p == 0:
                x //= p
                cnt += 1
            if cnt > best[i]:
                best[i] = cnt

    lcm = 1
    for p, e in zip(primes, best):
        lcm *= p ** e

    ans = 0
    for x in a:
        ans += lcm // x

    print(ans)

if __name__ == "__main__":
    solve()

The first loop extracts prime exponents. Because the numbers are tiny, repeated division is faster and simpler than storing a general factorization structure.

The variable best stores the LCM information. For each prime, it remembers the largest exponent encountered so far. The LCM reconstruction multiplies each prime by its stored exponent exactly once.

The final loop uses integer division because the LCM is guaranteed to be divisible by every input value. Python integers also avoid overflow issues, although the final answer remains small enough for typical competitive programming limits because the maximum LCM of numbers up to 20 is limited.

Worked Examples

For the input:

6
1 2 3 4 5 6

The LCM becomes 60.

Value	Required product	Computed B	Running sum
1	60	60	60
2	60	30	90
3	60	20	110
4	60	15	125
5	60	12	137
6	60	10	147

The result is:

This demonstrates that the common product must satisfy every element, not just the largest element.

For the input:

3
2 4 8

The maximum power of two is 2^3, so the LCM is 8.

Value	LCM	B value	Running sum
2	8	4	4
4	8	2	6
8	8	1	7

The answer is:

This confirms that repeated factors are handled through prime exponents.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Each number is factored using only the eight possible primes.
Space	O(1)	Only the prime exponent array and a few variables are stored.

The algorithm easily fits the constraints because it performs a constant amount of work for each of the 200000 input values.

Test Cases

import sys, io

def run(inp: str) -> str:
    old_stdin = sys.stdin
    sys.stdin = io.StringIO(inp)

    def solve():
        import sys
        input = sys.stdin.readline

        n = int(input())
        a = list(map(int, input().split()))

        primes = [2, 3, 5, 7, 11, 13, 17, 19]
        best = [0] * len(primes)

        for x in a:
            for i, p in enumerate(primes):
                cnt = 0
                while x % p == 0:
                    x //= p
                    cnt += 1
                best[i] = max(best[i], cnt)

        lcm = 1
        for p, e in zip(primes, best):
            lcm *= p ** e

        print(sum(lcm // x for x in a))

    solve()
    sys.stdin = old_stdin
    return sys.stdout.getvalue()

assert run("""6
1 2 3 4 5 6
""") == "147\n", "sample 1"

assert run("""3
2 4 8
""") == "7\n", "prime powers"

assert run("""1
20
""") == "1\n", "single element"

assert run("""5
7 7 7 7 7
""") == "5\n", "all equal values"

assert run("""8
1 2 3 4 5 6 10 20
""") == "210\n", "mixed factors"

Test input	Expected output	What it validates
`6 / 1 2 3 4 5 6`	`147`	Original sample behavior
`3 / 2 4 8`	`7`	Maximum prime power handling
`1 / 20`	`1`	Minimum size input
`5 / 7 7 7 7 7`	`5`	Equal values
`8 / 1 2 3 4 5 6 10 20`	`210`	Combining several prime factors

Edge Cases

For the repeated-value case:

3
2 2 2

The algorithm finds that the largest exponent of prime 2 is one, so the LCM is 2. Each value contributes 2 / 2 = 1, giving the answer 3. The method never multiplies duplicate values together, so it avoids overestimating the target.

For the prime-power case:

3
2 4 8

The factor counts are 2^1, 2^2, and 2^3. The stored maximum exponent is three, producing an LCM of 8. The contributions are 4, 2, and 1, giving the minimum possible sum 7.

For a single element:

1
15

The LCM of one number is the number itself. The only possible choice is B_1 = 1, so the answer is 1. The algorithm naturally handles this because no comparison with other values is needed.

CF 106351H - Fady mesh fady