(Dies ist abgeleitet von einem kürzlich abgeschlossenen Programmierwettbewerb)
Sie erhalten zwei Arrays von 10 ^ 5 ints im Bereich 1..10 ^ 7 inklusive:
%Vor% Stellen Sie sich vor, die rationale Zahl X sei das Ergebnis der Multiplikation aller Elemente von N und der Division durch alle Elemente von D.Ändern Sie die beiden Arrays, ohne den Wert von X zu ändern (und ohne irgendein Element außerhalb des Bereichs zu setzen), so dass das Produkt von N und das Produkt von D keinen gemeinsamen Faktor haben.
Eine naive Lösung (denke ich) würde funktionieren ...
%Vor%... aber das ist zu langsam.
Was ist eine Lösung, die weniger als etwa 10 ^ 9 Operationen benötigt?
Faktorisieren Sie alle Zahlen im Bereich von 1 bis 10 7 . Mit einer Modifikation eines Siebs von Eratosthenes können Sie alle Zahlen von 1 bis Besser als das ist wahrscheinlich eine Anordnung von nur die kleinsten Primfaktoren. n in O(n*log n) time (ich denke, es ist ein bisschen besser, O(n*(log log n)²) oder so) mit O(n*log log n) space faktorisieren.
Um eine Zahl n > 1 mit diesem Sieb zu faktorisieren, suchen Sie ihren kleinsten Primfaktor p , bestimmen Sie ihre Multiplizität in der Faktorisierung von n (entweder durch rekursives Nachschlagen oder durch einfaches Dividieren bis p doesn) teile den verbleibenden Cofaktor, der schneller ist, nicht mehr auf und den Cofaktor. Während der Cofaktor größer als 1 ist, suchen Sie den nächsten Primfaktor auf und wiederholen Sie den Vorgang.
Erstellen Sie eine Karte von Primzahlen zu Ganzzahlen
Gehen Sie durch beide Felder, für jede Zahl in N , addieren Sie den Exponenten jeder Primzahl in seiner Faktorisierung zum Wert in der Karte, für die Zahlen in D , subtrahieren Sie
Gehen Sie durch die Karte, wenn der Exponent der Primzahl positiv ist, geben Sie p^exponent in das Array N ein (möglicherweise müssen Sie das auf mehrere Indizes aufteilen, wenn der Exponent zu groß ist, und für kleine Werte kombinieren mehrere Primzahlen in einen Eintrag - es gibt 664579 Primzahlen weniger als 10 7 , so dass die 100.000 Schlitze in den Arrays möglicherweise nicht genug sind, um jedes Prim mit der richtigen Potenz zu speichern), wenn der Exponent negativ ist, mach dasselbe mit dem Array D , wenn es 0 ist, ignoriere dieses Prim.
Alle ungenutzten Slots in N oder D werden dann auf 1 gesetzt.
Faktorisieren Sie jedes Element eines Arrays, sortieren Sie es, löschen Sie es. Die Faktorisierung ist eine konstante Zeit für Bits begrenzter Größe, die Sortierung ist n log n und die Löschung wird linear sein. Die konstanten Faktoren können jedoch groß sein.
Wenn Sie eine niedrigere tatsächliche Ausführungszeit anstelle einer niedrigeren asymptotischen Komplexität anstreben, würde es wahrscheinlich nicht schaden, die Arrays durch manuelle Aufhebung kleiner Faktoren wie Potenzen von 2, 3, 5 und 7 vorzuverarbeiten Wahrscheinlichkeit (dh außer für pathologische Eingaben), wird dies die meisten Algorithmen immens beschleunigen, auf Kosten einiger linearer Zeitdurchläufe.
Eine weitere ausgeklügelte Methode, die die oben genannten Ansätze integriert, wäre, zunächst eine Liste von Primzahlen bis zu sqrt(10^7) ~= 3162 zu erstellen. Es sollte etwa 3162/ln(3162) ~= 392 solcher Primzahlen geben, nach dem Primzahlsatz. (Um die Laufzeit zu sparen, könnte / sollte diese Tabelle vorberechnet werden.)
Reduziere dann für jede solche ganze Zahl in N und für jede Primzahl die ganze Zahl um diese Primzahl, bis sie nicht mehr gleichmäßig verteilt ist, und jedes Mal eine Zählung für diese Primzahl. Machen Sie dasselbe für D , dekrementieren Sie stattdessen. Sobald Sie durch die Tabelle der Primzahlen gegangen sind, wird das aktuelle int nicht-1 sein, wenn und nur wenn es eine Primzahl größer als 3162 ist. Dies sollte etwa 7% der gesamten Ganzzahlen in jedem Array sein. Sie können diese in einem Haufen oder dergleichen aufbewahren. Setzen Sie sie im Array auch auf Einsen, während Sie weitermachen.
Schließlich iterieren Sie über die positiven Faktoren und fügen ihr Produkt in N ein. Sie müssen das wahrscheinlich über mehrere Array-Slots aufteilen, was in Ordnung ist. Setzen Sie die negativen Faktoren in D, und Sie sind fertig!
Die Laufzeit braucht dafür eine Minute. Hoffentlich ist es vernünftig.
Lässt Primfaktor jedes Element in N & amp; D in O (sqrt (10 ^ 7) * 10 ^ 5) als
%Vor%Pflegen Sie 2 Power-Arrays wo
%Vor% Fast alles wurde geschrieben, würde ich vorschlagen
Sei p = (Multiplikation aller Elemente in N)
Sei q = (Multiplikation aller Elemente in D)
X = (p / q); sollte immer konstant sein
finde Primfaktoren von p, q;
indem sie möglicherweise ihre Macht in einer Matrix a [0] (Potenz von 2), a [1] (Potenz von 3), a [2] (Potenz von 5) und so weiter speichern.
Jetzt können Sie die Werte in der Matrix vergleichen und die Leistung der unteren auf Null reduzieren.
z.B. p = 1280 q = 720
für p a [0] = 8 (Potenz von 2) a [1] = 0 (Potenz von 3) a [2] = 1 (Potenz von 5);
für q b [0] = 4 b [1] = 2 b [2] = 1;
mach eins / beide (falls beide gleich sind) Wert / s Null für den Index 0,1,2 .......
Tags und Links algorithm c math factorization