소개

AtCoder등의 경기 프로그래밍 문제를 풀고 있을 때, 「소인수 분해는 이미 알고 있기 때문에, 이것을 조합해 약수를 생성하고 싶다」라고 하는 것을 하고 싶어지는 경우가 있습니다.
그 방법에 대해, 가르친 & 생각한 내용을 정리했습니다.

문제

이러한 문제를 생각합니다.

문제
$N$ 개의 정수로 구성된 $A$ 열이 있습니다.
수열 $A$ 의 곱 $A_1 ​​* A_2 * ... * A_N$ 를 $X$ 로 할 때, $X$ 의 약수를 모두 출력해 주세요.

제약

$N <= 2 * 10^5$

$A_i <= 2 * 10^5$

$X <= 10^{18}$

입력 형식

N
A1 ... AN

샘플

입력

3
2 2 3

Output

1
2
3
4
6
12

소박한 해법

소박하게는, 우선 곱 $X$ 를 요구하고 나서, $2$ ~ $\sqrt X$ 의 범위에서 시험해 나누면 됩니다만,
시험 할인의 계산량은 $O(\sqrt N)$ 이므로, 곱 $X$ 가 거대한 경우에 계산량이 커져 버립니다.

X의 소인수분해를 구한다

여기서 곱 $X$ 를 직접 구하는 대신 곱 $X$ 의 소인수분해 를 구하는 것을 생각합니다.
다음 그림과 같이 자연수의 곱셈은 소인수의 병합임을 이용합니다.



즉, 수열 $A$ 의 각 요소 마다 소인수분해를 해, 그 결과의 지수부를 더해 병합합니다.
이것은 $O(N *\sqrt {maxA})$ 로 구할 수 있어 이번 제약하에서 고속으로 구합니다.

from collections import defaultdict
def prime_factors_from_list(A):
    """
    数列Aの全要素を掛けた数の素因数分解を求めます。
    """
    # 数列Aの各要素を素因数分解しながらマージする。
    # 素因数の辞書を1つ用意し、各要素について素因数を発見するたびに追加していく。
    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]))
""" (出力結果。 2^2 * 3^2 * 5^1 という素因数分解を表します。)
defaultdict(<class 'int'>, {2: 2, 3: 2, 5: 1})
"""

소인수분해에서 약수를 열거

이와 같이 구한 곱 $X$ 의 소인수분해에서 약수 리스트를 구하려면 어떻게 해야 할까요?

예를 들어, $12$ 의 소인수분해는 $2^2 * 3^1$ 이며 약수는 $1,2,3,4,6,12$ 의 6개입니다.
이것은 다음과 같이 각 소인수에 대한 지수 선택 방법의 패턴과 연관 될 수 있습니다.

$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$

소인수 $2$의 지수는 $0,1,2$의 3가지, $3$의 지수는 $0,1$의 2가지이므로,
$3*2=6$개의 약수를 얻을 수 있습니다.

이 사고 방식은 알려진 약수 각각에 대해 지금 주목하고 있는 소인수를 곱한 것을 찾아서 약수 리스트에 추가하는 작업의 반복으로서 구현할 수 있습니다.

def divisors_from_prime_factors(prime_factors, need_sort=True):
    """
    素因数分解から約数リストを生成します。(1とその数自身を含む)

    Parameters
    ---
    prime_factors
        素因数分解を表現した、タプルのリスト。
        p1^a1 * p2^a2 であれば、 [(p1,a1),(p2,a2)] 。
    need_sort
        Trueの場合、約数リストをソートして返します。
    """
    # 既知の約数リスト
    div = [1]
    for p,a in prime_factors:
        # 既知の約数それぞれに対して、
        # p^1倍, p^2倍, ... p^a倍 したものを計算して約数リストに追加する
        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

완성

위의 함수를 사용하여 다음과 같이 첫 번째 문제가 해결되었습니다.

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