Hallo. Ich habe mit diesem Problem während des Wettbewerbs und TLE eine Doppelschleife gemacht. Ich erinnere mich noch nicht an den grundlegenden Algorithmus, daher möchte ich ihn richtig verwenden können. Dieses Problem scheint viel Rechenaufwand zu ersparen, wenn Sie dasselbe Prinzip wie das Eratostenes-Sieb verwenden.
code.py
N = int(input())
A = list(map(int, input().split()))
A.sort() #Sortieren zum Sieben von Elatostines
Amax = A[-1]
dp = [1]*(Amax+1) #Machen Sie ein Sieb von Eratostenes bis zum Maximalwert von A.
ans = 0
for i in range(len(A)-1):
p = A[i]
if dp[p] == 1: #A[i]Ist ein[j]Überprüfen Sie, ob es sich um ein Vielfaches von handelt
for q in range(Amax//p+1):
dp[p*q] = 0 #A[i]Stellen Sie alle Vielfachen von ein
if A[i] != A[i+1]:
ans += 1 #A[i]Zählen, wenn sich nicht überlappt
if dp[Amax] == 1: #Da der Bereich bei der Suche nach Duplikaten überschritten ist, wird nur Amax separat beurteilt.
ans += 1
print(ans)
dp ist im Ausgangszustand dp = [1 1 1 1 1 1 1 ...].
Zum Beispiel Wenn A [0] = 3 ist, ist der dp nach einer Operation dp = [0 1 1 0 1 1 0 ...].
Recommended Posts