introduction

Lors de la résolution de problèmes de programmation compétitifs tels qu'AtCoder, vous voudrez peut-être faire quelque chose comme "Je connais déjà la décomposition des facteurs premiers, donc je veux la combiner pour générer une fraction." J'ai résumé ce que j'ai appris et réfléchi à la manière de le faire.

problème

Considérez un tel problème.

** Problème ** Il existe une séquence de $ A $ constituée d'entiers $ N $. Lorsque le produit de la séquence $ A $ $ A_1 * A_2 * ... * A_N $ est $ X $, sortez toutes les fractions de $ X $.

** Contraintes **

N <= 2 * 10^5

A_i <= 2 * 10^5

X <= 10^{18}

** Format d'entrée **

N
A1 ... AN

**Sample**

Input

3
2 2 3

Output

Solution simple

Pour être simple, vous pouvez d'abord trouver le produit $ X $, puis essayer de le diviser dans la plage de $ 2 $ à $ \ sqrt X $. Étant donné que le montant du calcul pour la division d'essai est de $ O (\ sqrt N) $, le montant du calcul sera important si le produit $ X $ est énorme.

Trouvez la factorisation première de X

Pensez maintenant à rechercher la ** factorisation première du produit $ X $ ** au lieu de trouver directement le produit $ X $. Comme le montre la figure suivante, ** la multiplication des nombres naturels profite du fait qu'elle est une fusion de facteurs premiers **.

En d'autres termes, chaque élément de la séquence $ A $ est factorisé en facteurs premiers, et les ** exposants résultants sont additionnés ** pour les fusionner. Cela peut être calculé avec $ O (N * \ sqrt {maxA}) $, qui peut être calculé rapidement sous cette contrainte.

from collections import defaultdict
def prime_factors_from_list(A):
    """
Trouvez la factorisation première du nombre multipliée par tous les éléments de la suite A.
    """
    #Fusionnez chaque élément de la séquence A tout en le factorisant en facteurs premiers.
    #Préparez un dictionnaire des facteurs premiers et ajoutez-le chaque fois que vous découvrez un facteur premier pour chaque élément.
    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]))
""" (Résultat de sortie. 2^2 * 3^2 * 5^Représente une factorisation première de 1.)
defaultdict(<class 'int'>, {2: 2, 3: 2, 5: 1})
"""

Lister les réductions de la factorisation prime

Comment obtenir une liste de diviseurs à partir de la factorisation première du produit $ X $ ainsi obtenu?

Par exemple, la factorisation première de $ 12 $ est 2 $ ^ 2 * 3 ^ 1 $, et les six fractions sont $ 1,2,3,4,6,12 $. Ceci peut être associé à ** un modèle de sélection exponentielle pour chaque facteur premier ** comme suit:

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

Le facteur premier $ 2 $ a trois exposants de 0,1,2 $ et l'exposant $ 3 $ a deux exposants de 0,1 $. Nous avons obtenu 3 $ * 2 = 6 $ fractions.

Cette idée peut être mise en œuvre comme une tâche répétitive de ** chaque fraction connue multipliée par le premier facteur d'intérêt et ajoutée à la liste des fractions **.

def divisors_from_prime_factors(prime_factors, need_sort=True):
    """
Génère une liste de réductions à partir de la factorisation des nombres premiers.(Comprend 1 et son numéro lui-même)
    
    Parameters
    ---
    prime_factors
Une liste de taples qui représentent la factorisation principale.
        p1^a1 * p2^Si a2,[(p1,a1),(p2,a2)] 。
    need_sort
Si True, trie et renvoie la liste des fractions.
    """
    #Liste des fractions connues
    div = [1]
    for p,a in prime_factors:
        #Pour chaque fraction connue
        # p^1 fois, p^2 fois, ... p^Calculer un temps et ajouter à la liste de réduction
        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

Achevée

En utilisant la fonction ci-dessus, le problème au début a été résolu comme suit.

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