[GO] Ungefähre Aufzählung, wenn die Primfaktorisierung bereits bekannt ist (Python)

Einführung

Wenn Sie wettbewerbsfähige Programmierprobleme wie AtCoder lösen, möchten Sie möglicherweise Folgendes tun: "Ich kenne die Zerlegung des Primfaktors bereits, daher möchte ich sie kombinieren, um einen Bruch zu erzeugen." Ich habe zusammengefasst, was ich gelernt und darüber nachgedacht habe, wie es geht.

Problem

Betrachten Sie ein solches Problem.

** Problem ** Es gibt eine Folge von $ A $, die aus $ N $ ganzen Zahlen besteht. Wenn das Produkt der Sequenz $ A $ $ A_1 * A_2 * ... * A_N $ $ X $ ist, geben Sie alle Brüche von $ X $ aus.

** Einschränkungen **

• N <= 2 * 10^5
• A_i <= 2 * 10^5
• X <= 10^{18}

** Eingabeformat **

N
A1 ... AN

3
2 2 3

1
2
3
4
6
12

Einfache Lösung

Um es einfach zu machen, können Sie zuerst das Produkt $ X $ finden und dann versuchen, es im Bereich von $ 2 $ bis $ \ sqrt X $ zu teilen. Da der Rechenaufwand für die Testaufteilung $ O (\ sqrt N) $ beträgt, ist der Rechenaufwand groß, wenn das Produkt $ X $ sehr groß ist.

Finden Sie die Primfaktorisierung von X.

Betrachten Sie nun die ** Primfaktorisierung des Produkts $ X $ **, anstatt das Produkt $ X $ direkt zu finden. Wie in der folgenden Abbildung gezeigt, nutzt die ** Multiplikation natürlicher Zahlen die Zusammenführung von Primfaktoren **.

Mit anderen Worten, jedes Element der Sequenz $ A $ wird in Primfaktoren zerlegt, und die resultierenden ** Exponenten werden addiert **, um sie zusammenzuführen. Dies kann mit $ O (N * \ sqrt {maxA}) $ berechnet werden, was unter dieser Bedingung schnell berechnet werden kann.

from collections import defaultdict
def prime_factors_from_list(A):
    """
Finden Sie die Primfaktorisierung der Zahl multipliziert mit allen Elementen der Sequenz A.
    """
    #Führen Sie jedes Element der Sequenz A zusammen, während Sie es in Primfaktoren zerlegen.
    #Bereiten Sie ein Wörterbuch mit Primfaktoren vor und fügen Sie es jedes Mal hinzu, wenn Sie für jedes Element einen Primfaktor ermitteln.
    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]))
""" (Ausgabeergebnis. 2^2 * 3^2 * 5^Stellt eine Primfaktorisierung von 1 dar.)
defaultdict(<class 'int'>, {2: 2, 3: 2, 5: 1})
"""

Listen Sie die Reduktionen aus der Primfaktorisierung auf

Wie können wir eine Liste von Teilern aus der Primfaktorisierung des auf diese Weise erhaltenen Produkts $ X $ erhalten?

Zum Beispiel ist die Primfaktorisierung von $ 12 $ $ 2 ^ 2 * 3 ^ 1 $, und die sechs Brüche sind $ 1,2,3,4,6,12 $. Dies kann wie folgt mit ** einem Muster exponentieller Auswahl für jeden Primfaktor ** verbunden werden:

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

Der Primfaktor $ 2 $ hat drei Exponenten von $ 0,1,2 $, und der Exponent $ 3 $ hat zwei Exponenten von $ 0,1 $. Wir haben $ 3 * 2 = 6 $ Brüche erhalten.

Diese Idee kann als sich wiederholende Aufgabe von ** jeder bekannten Fraktion multipliziert mit dem interessierenden Hauptfaktor implementiert und zur Liste der Fraktionen ** hinzugefügt werden.

def divisors_from_prime_factors(prime_factors, need_sort=True):
    """
Erzeugt eine Liste der Reduzierungen aus der Primfaktorisierung.(Beinhaltet 1 und seine Nummer selbst)
    
    Parameters
    ---
    prime_factors
Eine Liste von Taples, die die Primfaktorisierung darstellen.
        p1^a1 * p2^Wenn a2,[(p1,a1),(p2,a2)] 。
    need_sort
Wenn True, wird die Bruchliste sortiert und zurückgegeben.
    """
    #Liste bekannter Fraktionen
    div = [1]
    for p,a in prime_factors:
        #Für jede bekannte Fraktion
        # p^1x, p^2 Mal, ... p^Berechnen Sie eine Zeit und fügen Sie sie der Reduktionsliste hinzu
        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

Komplett

Mit der obigen Funktion wurde das Problem am Anfang wie folgt gelöst.

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