[Python] Wie man den Bruchteil einer natürlichen Zahl mit hoher Geschwindigkeit erhält
Einführung
Vielen Dank für das Lesen dieses Artikels! !! Dies ist ** Nakazon **, der im Juni 2020 sein Programmdebüt feierte!
Es ist meine tägliche Routine, mindestens 5 AtCorder A-D-Probleme zu lösen.
In meinem Artikel aus der Sicht eines Programmieranfängers Lernen und Schwierigkeiten, die durch tägliche Routinen entdeckt wurden Ich möchte Ihnen sagen, worüber ich mich gefreut habe.
Ich werde versuchen, einen Artikel zu schreiben, den die gleichen Anfänger lernen können! Fortgeschrittene beobachten mit warmen Augen und Wir freuen uns auf Ihre positive Weisheit und Beratung!
Kommen wir zum heutigen Inhalt! !!
Problem
Klicken Sie hier für die Probleme, die zum heutigen Lernen geführt haben
C - Walk on Multiplication Table https://atcoder.jp/contests/abc144/tasks/abc144_c
Unter Berücksichtigung von N = 10 im Beispiel gibt es zwei Kandidaten für i und j, (1, 10) und (2, 5). Betrachten Sie die Kombination von i und j, die N = i * j mit dem kleinsten i + j erfüllt. Dann, als ich dachte: "Lass uns die Nummer holen!" Ich falle in den Zustand "Was? Was soll ich tun?" .. .. Lol
So erhält man den Bruchteil der natürlichen Zahl N! !!
Da N maximal 10 ** 12 ist, ist es nicht möglich, alle von 1 mit einer for-Anweisung zu suchen Es dauert zu lange, also müssen Sie es sich ausdenken.
qiita.rb
N = int(input())
divisors = []
for i in range(1, int(N**0.5)+1):
if N % i == 0:
divisors.append(i)
if i != N // i:
divisors.append(N//i)
divisors.sort()
Wenn Sie so nach √N (dem Wendepunkt der Zahl) suchen Der Punkt ist, dass Sie alle Brüche erhalten können.
Schließlich
Ich möchte eine Person sein, die mit einem solchen Algorithmuselement bemerkt. Es ist erstaunlich zu bemerken