Énumération approximative lorsque la factorisation des nombres premiers est déjà connue (Python)

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

1
2
3
4
6
12

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 **.

image.png

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

Recommended Posts

Énumération approximative lorsque la factorisation des nombres premiers est déjà connue (Python)
Mémo Python d'énumération approximative
[Python 3] Décomposition des facteurs premiers en 14 lignes
python Remarque: lorsque easy_install ne peut pas être utilisé
[Pour les professionnels de la concurrence] Résumé des facteurs premiers, des réductions et des facteurs premiers
Énumération des nombres premiers et jugement des nombres premiers en Python
Décomposition en facteurs premiers ver.1 des entiers entrés en Python
Décomposition en facteurs premiers ver.2 des entiers entrés en Python
Juger s'il s'agit d'un nombre premier [Python]