[PYTHON] Berechnen des aus ABC134-D gelernten Rechenaufwands

Problem

https://atcoder.jp/contests/abc134/tasks/abc134_d

war schwierig. Oder besser gesagt, es war schwierig, die Problemstellung zu lesen.

Diese Lektion

Beliebige Ganzzahl = Nuance wie alle Ganzzahlen
Eindeutig bestätigt durch Lösen in der Reihenfolge von hinten
O(\sum(N/i)) = O(NlogN)

So berechnen Sie den Berechnungsbetrag

Frage aufgeworfen: Ist $ O (\ sum (N / i)) $ rechtzeitig?

In diesem Problem ist es notwendig, $ N / i $ bei jedem i zu finden. Wenn Sie dies berücksichtigen, ist es gut, eine Integration durchzuführen. Da $ \ int (1 / N) = logN $ ist, kann es im schlimmsten Fall durch logN unterdrückt werden.

Zusammenfassung

Werden Sie ein mathematischer Satz
Es ist üblich, die Reihenfolge von vorne oder hinten zu beurteilen, und Sie müssen sich dessen bewusst sein.
** In Anbetracht der Integration kann die Berechnungszeit aus dem Bereich abgerufen werden. ** ** **

Code

N = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
b = [0] * N
M = 0
for i in range(N, 0, -1):
    ball = 0
    for j in range(i + i, N + 1, i):
        ball ^= b[j - 1]
    b[i - 1] = ball ^ a[i]
M = sum(b)
print(M)
for i in range(N):
    if b[i]:
        print(i + 1, end = ' ')

Recommended Posts

Berechnen des aus ABC134-D gelernten Rechenaufwands

Wie berechnet man den Autokorrelationskoeffizienten?

So ermitteln Sie die durchschnittliche Informationsmenge (Entropie) der ursprünglichen Wahrscheinlichkeitsverteilung aus der Stichprobe

So überprüfen Sie die Version von Django

Berechnen Verwenden Sie% des Befehls df

So bedienen Sie Linux von der Konsole aus

So greifen Sie von außen auf den Datenspeicher zu

Von der Einführung der GoogleCloudPlatform Natural Language API bis zur Verwendung

So finden Sie den Bereich des Boronoi-Diagramms

Ändern Sie den Dezimalpunkt der Protokollierung von, nach.

So bedienen Sie Linux von außen Vorgehensweise

So messen Sie die Leitungsgeschwindigkeit vom Terminal aus

Von der Einführung von Pyethapp bis zur Vertragsabwicklung

Die Geschichte vom Umzug von Pipenv zur Poesie

[Numpy, scipy] Wie berechnet man die Quadratwurzel einer Elmeet-Matrix mit halbregelmäßigem Wert?

[Python] So entfernen Sie doppelte Werte aus der Liste

Wie man die Portnummer des xinetd-Dienstes kennt

Die Wand beim Ändern des Django-Dienstes von Python 2.7 auf Python 3-Serie

Berechnen Sie das Volumen aus der zweidimensionalen Struktur einer Verbindung

So ermitteln Sie die Anzahl der Stellen in Python

Berechnung der minimal erforderlichen Stimmenzahl aus der Stimmenzahl

So lösen Sie die rekursive Funktion, die abc115-D gelöst hat

Tensorflows Denkweise lernte aus der Kartoffelherstellung

So starten Sie Jupyter Notebook sofort vom Terminal aus

Schritte zur Berechnung der Wahrscheinlichkeit einer Normalverteilung

[Blender] So legen Sie die Auswahlelemente von EnumProperty dynamisch fest

[Python] Zusammenfassung, wie die Farbe der Figur angegeben wird

Verwendung des in Lobe in Python erlernten Modells

Wie man das Dokument der magischen Funktion (Linienmagie) trifft

So greifen Sie auf die globale Variable des importierten Moduls zu

So veröffentlichen Sie ein Ticket über die Shogun-API

[Selen] Wie wird der relative Pfad des Chromedriver angegeben?

[Python] Berechnungsmethode der Approximationsformel von Abschnitt 0 wie Excel [scikit-learn] Memo

Zusammenfassung von Anfang bis Kapitel 1 der Einführung in Entwurfsmuster, die in der Java-Sprache gelernt wurden

So erhöhen Sie die Verarbeitungsgeschwindigkeit der Erfassung der Scheitelpunktposition

[Ubuntu] So löschen Sie den gesamten Inhalt des Verzeichnisses

So testen Sie die Attribute, die durch add_request_method of pyramid hinzugefügt wurden

Verwendung des Generators

So melden Sie sich automatisch wie 1Password von der CLI an

(Hinweis) So übergeben Sie den Pfad Ihres eigenen Moduls

Ich möchte die zulässige Ausfallzeit aus der Betriebsrate berechnen

So kratzen Sie mit Python den Aktienkurs einer einzelnen Aktie von der Nikkei Shimbun-Website

Wie kann man schnell die Häufigkeit des Auftretens von Zeichen aus einer Zeichenfolge in Python zählen?

So nehmen Sie erste Einstellungen für die Django-Projekterstellung vor

Wie man die Ergebnisse von FreeSurfer ~ aparc, aseg, wmparc ~ zusammenfasst

So führen Sie die Exportfunktion des GCP-Datenspeichers automatisch aus

So berechnen Sie die Summe oder den Durchschnitt von Zeitreihen-CSV-Daten in einem Augenblick

So erhöhen Sie die Anzahl der Datensatzbilder für maschinelles Lernen

Wie man die Anzahl der GPUs aus Python kennt ~ Hinweise zur Verwendung von Multiprocessing mit pytorch ~

Wie man NAPALM aus dem Web erreicht (NetDevOpsSec echte Lösung)

So sehen Sie den Inhalt der ipynb-Datei des Jupyter-Notizbuchs

Die Geschichte des Kopierens von Daten von S3 auf Googles TeamDrive

So ermitteln Sie den Skalierungskoeffizienten eines bipolaren Wavelets

Berechnen Sie die Anzahl der Änderungen

Immerhin die Geschichte der Rückkehr von Linux zu Windows

Darstellung der Verteilung der Bakterienzusammensetzung aus Qiime2-Analysedaten in einem Box-Whisker-Diagramm

Wie benutzt man den Dekorateur?

So erhalten Sie eine Liste mit Links von einer Seite aus Wikipedia

So erhöhen Sie die Achse

So starten Sie die erste Projektion