Introduction

When solving competitive programming problems such as AtCoder, you may want to do something like "I already know the prime factorization, so I want to combine it to generate a divisor." I have summarized what I learned & thought about how to do it.

problem

Consider such a problem.

** Problem ** There is a sequence $ A $ consisting of $ N $ integers. When the product $ A_1 * A_2 * ... * A_N $ of the sequence $ A $ is $ X $, output all the divisors of $ X $.

** Constraints **

N <= 2 * 10^5

A_i <= 2 * 10^5

X <= 10^{18}

** Input format **

N
A1 ... AN

**Sample**

Input

3
2 2 3

Output

Simple solution

To be simple, you can first find the product $ X $ and then try and divide it in the range of $ 2 $ to $ \ sqrt X $. Since the calculation amount of trial division is $ O (\ sqrt N) $, the calculation amount becomes large when the product $ X $ is huge.

Find the prime factorization of X

Now consider finding the ** prime factorization of the product $ X $ ** instead of finding the product $ X $ directly. As shown in the following figure, ** multiplication of natural numbers takes advantage of the fact that it is a merge of prime factors **.

In other words, factorize each element of the sequence $ A $ into prime factors, and then add the ** exponents of the result ** to merge them. This can be calculated by $ O (N * \ sqrt {maxA}) $, which can be calculated at high speed under this constraint.

from collections import defaultdict
def prime_factors_from_list(A):
    """
Find the prime factorization of the number multiplied by all the elements of the sequence A.
    """
    #Merge each element of the sequence A while factoring it into prime factors.
    #Prepare one dictionary of prime factors and add it each time you discover a prime factor for each element.
    prime_factors = defaultdict(int)
    for a in A:
        tmp = a
        factor = 2
        while factor ** 2 <= a and tmp != 1:
            while tmp % factor == 0:
                a_is_prime = False
                prime_factors[factor] += 1
                tmp //= factor
            # 2,3,5,7,9...
            factor += (1 if factor == 2 else 2)
        if tmp != 1:
            prime_factors[tmp] += 1
    return prime_factors

print(prime_factors_from_list([12,15]))
""" (Output result. 2^2 * 3^2 * 5^Represents a prime factorization of 1.)
defaultdict(<class 'int'>, {2: 2, 3: 2, 5: 1})
"""

List divisors from prime factorization

How can we find the divisor list from the prime factorization of the product $ X $ obtained in this way?

For example, the prime factorization of $ 12 $ is $ 2 ^ 2 * 3 ^ 1 $, and the divisors are six, $ 1,2,3,4,6,12 $. This can be associated with ** a pattern of exponential selection for each prime factor ** as follows:

1 = 2^0 * 3^0 2 = 2^1 * 3^0 3 = 2^0 * 3^1 4 = 2^2 * 3^0 6 = 2^1 * 3^1 12 = 2^2 * 3^1

The prime factor $ 2 $ has three exponents of $ 0,1,2 $, and the $ 3 $ exponent has two exponents of $ 0,1 $. We have obtained $ 3 * 2 = 6 $ divisors.

This idea can be implemented as a repetition of ** each known divisor multiplied by the prime factor of interest and added to the divisor list **.

def divisors_from_prime_factors(prime_factors, need_sort=True):
    """
Generate a divisor list from prime factorization.(Includes 1 and its number itself)
    
    Parameters
    ---
    prime_factors
A list of tuples that represent the prime factorization.
        p1^a1 * p2^If a2,[(p1,a1),(p2,a2)] 。
    need_sort
If True, sorts and returns the divisor list.
    """
    #List of known divisors
    div = [1]
    for p,a in prime_factors:
        #For each of the known divisors
        # p^1x, p^2 times, ... p^Calculate a times and add to the divisor list
        m = len(div)
        for i in range(m):
            for j in range(1, a+1):
                div.append(div[i] * p**j)
    if need_sort:
        div.sort()
    return div

Complete

Using the above function, the problem at the beginning was solved as follows.

n = int(input())
A = list(map(int, input().split())
prime_factors = prime_factors_from_list(A)
divisors = divisors_from_prime_factors(prime_factors.items())
print(*divisors, sep="\n")