Counter in einer Sequenz zählen

Ich habe eine etwas schnellere Alternative gefunden, die auf Ihrer Antwort basiert. Auf meinem Arbeits-PC benötigt meine C ++ - Implementierung (unten) etwa 350ms , um eine Probleminstanz zu lösen. auf meinem alten Laptop dauert es etwas über 1s. Dieser Algorithmus vermeidet alle Divisions- und Modulo-Operationen und verwendet nur O (m) -Raum.

Wie bei Ihrem Algorithmus besteht die Grundidee darin, das Einschluss-Ausschluss-Prinzip anzuwenden, indem Sie jede Zahl 2 & lt; = i & lt; = m, die keine wiederholten Faktoren enthält, genau einmal aufzählen und für jedes solche i die Anzahl von zählen Zahlen in der Eingabe, die durch i teilbar sind und diese entweder addieren oder von der Summe subtrahieren. Der Hauptunterschied besteht darin, dass wir den Zählteil "dumm" machen können, indem wir einfach testen, ob jedes mögliche Vielfache von i in der Eingabe erscheint, und dies dauert immer noch nur O (m log m).

Wie oft wiederholt sich die innerste Zeile c += v[j].freq; in countCoprimes() ? Der Körper der äußeren Schleife wird einmal für jede Zahl 2 & lt; = i & lt; = m ausgeführt, die keine wiederholten Primfaktoren enthält; diese Iterationszahl ist trivialerweise höher als m. Die innere Schleife schreitet jeweils um i Schritte durch den Bereich [2..m] fort, so dass die Anzahl der Operationen, die sie während einer einzelnen äußeren Schleifeniteration ausführt, durch m / i begrenzt ist. Daher ist die Gesamtzahl der Iterationen der innersten Linie durch die Summe von i = 2 bis m von m / i begrenzt. Der m-Faktor kann außerhalb der Summe verschoben werden, um eine obere Grenze von

Diese Summe ist eine Teilsumme in einer harmonischen Reihe, und wird durch log (m ) , also ist die Gesamtzahl der innersten Schleifeniterationen O (m log m).

extendedEratosthenes() wurde entwickelt, um konstante Faktoren zu reduzieren, indem alle Unterteilungen vermieden und die O (m) Speicherauslastung beibehalten wird. Alle countCoprimes() müssen tatsächlich für eine Zahl 2 wissen & lt; = i & lt; = m ist (a) ob sie wiederholte Primfaktoren hat und wenn nicht, (b) ob sie eine gerade oder ungerade Anzahl von hat Primfaktoren. Um (b) zu berechnen, können wir die Tatsache nutzen, dass das Sieb von Eratosthenes effektiv jedes gegebene i mit seinen verschiedenen Primfaktoren in aufsteigender Reihenfolge "trifft", also können wir einfach ein bisschen drehen (das parity -Feld in struct entry ) um zu verfolgen, ob ich eine gerade oder ungerade Anzahl von Faktoren habe. Jede Zahl beginnt mit einem prod -Feld gleich 1; (a) wir "knock out" einfach jede Zahl, die das Quadrat einer Primzahl als Faktor enthält, indem wir ihr prod -Feld auf 0 setzen. Dieses Feld dient einem doppelten Zweck: Wenn v[i].prod == 0 , zeigt dies an, dass i wurde entdeckt, um wiederholte Faktoren zu haben; andernfalls enthält es das Produkt der (notwendigerweise unterschiedlichen) Faktoren, die bisher entdeckt wurden. Der (ziemlich geringfügige) Nutzen davon ist, dass es uns erlaubt, die Hauptsiebschleife an der Quadratwurzel von m zu stoppen, anstatt den ganzen Weg bis zu m zu gehen: für jedes gegebene i, das keine wiederholten Faktoren hat v[i].prod == i , in diesem Fall haben wir alle Faktoren für i oder v[i].prod < i gefunden. In diesem Fall muss ich genau einen Faktor haben & gt; sqrt (3000000), die wir noch nicht berücksichtigt haben. Wir können alle diese verbleibenden "großen Faktoren" mit einer zweiten, nicht verschachtelten Schleife finden.

Nachdem ich die Ideen, die ich in meiner Frage erwähnt habe, weiter ausgenutzt habe, habe ich es geschafft, selbst eine Lösung zu finden. Da einige von euch daran interessiert sind, werde ich es kurz beschreiben. Es funktioniert in O (m log m + n), ich habe es bereits in C ++ implementiert und getestet - löst die größten Fälle (10 ^ 6 ganze Zahlen) in weniger als 5 Sekunden.

Wir haben n ganze Zahlen, die nicht größer als m sind. Wir beginnen damit, dass Eratosthenes Sieve jede Integer-Zahl bis auf m zum kleinsten Primfaktor abbildet, sodass wir jede Zahl, die nicht größer als m ist, in O (log m) ausklammern können. Dann teilen wir für alle gegebenen Zahlen A [i], solange es ein Primzahl p gibt als A [i] in einer Potenz größer als Eins, A [i] damit, denn wenn wir fragen, ob zwei Zahlen Co-Rime sind, können wir Lassen Sie die Exponenten weg. Das lässt uns, dass alle A [i] Produkte von verschiedenen Primzahlen sind.

Ab jetzt werden wir nach dem Inklusion-Exklusion-Prinzip arbeiten. Nach T berechnen wir für jedes i P [i] - die Menge der Paare (j, k), so dass A [j] und A [k] beide durch i teilbar sind. Berechnen Sie dann die Antwort, summieren Sie alle P [i] und nehmen Sie ein Minuszeichen vor denen P [i], für die ich eine gerade Anzahl von Primordivisoren hat. Beachten Sie, dass alle Primzahlen von i verschieden sind, weil i P [i] für alle anderen Indizes gleich 0 ist. Durch Inklusion-Exclusion wird jedes Paar nur einmal gezählt. Um dies anders zu sehen, nehmen Sie ein Paar A [i] und A [j], vorausgesetzt, dass sie genau k gemeinsame Primzahlteiler teilen. Dann wird dieses Paar k-mal gezählt, dann kC2-mal diskontiert, kC3-mal gezählt, kC4-mal diskontiert ... für nCk siehe das Newton-Symbol. Einige mathematische Manipulationen lassen uns sehen, dass das betrachtete Paar 1 - (1-1) ^ k = 1 mal gezählt wird, was den Beweis abschließt.

Bisherige Schritte erforderten O (m log log m) für das Sieb und O (m) für die Berechnung des Ergebnisses. Das letzte, was zu tun ist, ist Array T zu konstruieren. Wir könnten für jedes A [i] nur T [j] für alle j teilen, die i teilen. Da A [i] höchstens O (sqrt (A [i])) Divisoren haben kann (und in der Praxis sogar weniger), könnten wir T in O (n sqrt m) konstruieren. Aber wir können es besser machen!

Man nehme ein zweidimensionales Array W. Zu jedem Zeitpunkt gilt eine folgende Invariante - wenn für jeden von Null verschiedenen W [i] [j] der Zähler in Tabelle T um W [i] [j] für alle Zahlen erhöht würde das teile ich, und teilen auch die genauen Exponenten, die ich in j kleinsten Primzahlteiler von i habe, dann würde T richtig konstruiert werden. Da dies ein wenig verwirrend erscheinen mag, sehen wir es in Aktion. Zu Beginn, um die Invariante wahr zu machen, erhöhen wir für jedes A [i] nur W [A [i]] [0]. Beachten Sie auch, dass eine Zahl, die nicht größer als m ist, höchstens O (log m) Primordivisoren haben kann, sodass die Gesamtgröße von W O (m log m) ist. Jetzt sehen wir, dass eine in W [i] [j] gespeicherte Information auf folgende Weise "vorwärtsgetrieben" werden kann: Betrachten wir p als (j + 1) -ten Primteiler von i, vorausgesetzt, dass es einen hat. Dann kann irgendein Divisor von i entweder p mit einem Exponenten haben, der gleich ist wie in i oder niedriger. Der erste dieser Fälle ist W [i] [j + 1] - wir fügen einen weiteren Prim hinzu, der von einem Divisor "vollständig" genommen werden muss. Der zweite Fall ist W [i / p] [j] als ein Teiler von i, der kein p mit einem höchsten Exponenten hat, muss auch i / p teilen. Und das ist es! Wir betrachten alles i in absteigender Reihenfolge, dann j in aufsteigender Reihenfolge. Wir "schieben" Informationen von W [i] [j]. Seht ihr, wenn ich genau j Prim Divisoren habe, dann können die Informationen nicht gepusht werden, aber das brauchen wir nicht wirklich! Wenn ich j Prim Divisoren habe, dann sagt W [i] [j] im Grunde: Inkrementieren um W [i] [j] nur Index i in Array T. Also, wenn alle Informationen zu geschoben wurde "letzte Zeilen" in jedem W [i] durchlaufen wir diese Zeilen und beenden die Konstruktion von T. Da jede Zelle von W [i] [j] einmal besucht wurde, benötigt dieser Algorithmus O (m log m) Zeit und auch O (n) am Anfang. Damit ist der Bau abgeschlossen. Hier ist ein C ++ - Code aus der aktuellen Implementierung:

Am Ende würde ich sagen, dass Array T schneller und einfacher konstruiert werden kann als das, was ich gezeigt habe. Wenn jemand eine nette Idee hat, wie es gemacht werden könnte, würde ich mich über alle Rückmeldungen freuen.

Hier ist eine Idee basierend auf der Formel für die vollständige Sequenz 1..n , gefunden auf Ссылка :

Iteriere über die Sequenz S . Für jeden Begriff S_i :

für jeden der Primfaktoren, p , von S_i :
wenn ein Hash für p nicht existiert:
Erstellen Sie einen Hash mit dem Index p , der auf eine Menge aller Indizes von S zeigt, mit Ausnahme von i ,
und ein auf 1 gesetzter Zähler, der angibt, wie viele Terme von S bis p teilbar sind sonst:
Löschen Sie i in der vorhandenen Menge von Indizes und inkrementieren Sie den Zähler

Sortiere die Hashes für die Primfaktoren von S_i nach ihren Zählern in absteigender Reihenfolge. Beginnend mit
Der größte Counter (dh der kleinste Satz) erstellt eine Liste von Indizes bis zu i , die auch ein
sind Mitglieder des nächstkleineren Satzes, bis die Sätze erschöpft sind. Fügen Sie die verbleibende Anzahl von
hinzu Indizes in der Liste auf die kumulative Summe.

Beispiel:

Ich würde vorschlagen:

1) Verwenden Sie Eratosthene, um eine Liste der sortierten Primzahlen unter 10 ^ 6 zu erhalten.

2) Für jede Zahl n in der Liste erhalten Sie die Primfaktoren. Ordnen Sie ihm eine andere Zahl f (n) folgendermaßen zu: Sagen wir, dass die Primfaktoren von n 3, 7 und 17 sind. Dann ist die binäre Darstellung von f (n):

Die erste Ziffer (hier 0) ist der Primzahl 2 zugeordnet, die zweite Ziffer (1 hier) ist der Primzahl 3 zugeordnet, usw. ...

Daher sind 2 Zahlen n und m Gemeinsamkeiten, wenn f (n) & amp; f (m) = 0 .

3) Es ist leicht zu erkennen, dass es für jedes n ein N gibt: f (n) & lt; = (2 ^ N) - 1. Dies bedeutet, dass die größte Zahl f (n) kleiner oder gleich ist eine Zahl, deren binäre Darstellung lautet:

Hier ist N die Zahl 1 in der obigen Reihenfolge. Holen Sie sich dieses N und sortieren Sie die Liste der Zahlen f (n). Nennen wir diese Liste L. Wenn Sie optimieren möchten: Speichern Sie in dieser Liste anstelle von Duplikaten ein Paar, das f (n) enthält, und die Anzahl der Wiederholungen von f (n).

4) Iterieren Sie von 1 nach N auf diese Weise: initialisieren Sie i = 1 0 0 0 0, und verschieben Sie bei jeder Iteration die Ziffer 1 nach rechts, wobei alle anderen Werte auf 0 bleiben (implementieren Sie sie mit Bitshift) / p>

Iteriere bei jeder Iteration über L, um die Anzahl d (i) der Elemente l in L zu erhalten, so dass i & amp; l! = 0 (Vorsicht, wenn Sie die obige Optimierung verwenden). Mit anderen Worten, für jedes i, hole die Anzahl der Elemente in L, die nicht mit i übereinstimmen, und nenne diese Zahl d (i). Fügen Sie den Gesamtwert hinzu

5) Diese Zahl D ist die Anzahl der Paare, die in der ursprünglichen Liste nicht identisch sind. Die Anzahl der Co-Paare ist:

wobei M die Anzahl der Elemente in der ursprünglichen Liste ist. Die Komplexität dieser Methode ist O (n log (n)).

Viel Glück!

Meine vorherige Antwort war falsch, Entschuldigung. Ich schlage hier eine Modifikation vor:

Sobald Sie die Primzahlteiler jeder Nummer der Liste erhalten haben, ordnen Sie jeder Primzahl p die Zahl l (p) der Zahlen in der Liste zu, die p als Divisor hat. Betrachten wir zum Beispiel die Primzahl 5, und die Nummer der Liste, die durch 5 geteilt werden kann, ist 15, 100 und 255. Dann l (5) = 3.

Um es in O (n logn) zu erreichen, iteriere über die Liste und iteriere für jede Zahl in dieser Liste über ihre Primfaktoren; erhöhe für jeden Primfaktor p sein l (p).

Dann ist die Anzahl der Paare, die nicht gemeinsam genutzt werden und durch p geteilt werden können,

Summiere diese Zahl für alle Primzahlen, und du erhältst die Anzahl der Paare in der Liste, die nicht gleichzeitig sind (beachte, dass l (p) 0 sein kann). Sagen wir, diese Summe ist D, dann ist die Antwort

wobei M die Länge der Liste ist. Viel Glück!