Bonjour. J'ai fait une double boucle avec ce problème pendant le concours et TLE. Je ne me souviens pas encore de l'algorithme de base, donc je veux pouvoir l'utiliser correctement. Ce problème semble économiser beaucoup de calculs si vous utilisez le même principe que le tamis Eratostenes.
code.py
N = int(input())
A = list(map(int, input().split()))
A.sort() #Trier pour le tamisage des élatostines
Amax = A[-1]
dp = [1]*(Amax+1) #Faites un tamis d'ératostènes jusqu'à la valeur maximale de A.
ans = 0
for i in range(len(A)-1):
p = A[i]
if dp[p] == 1: #A[i]Est un[j]Vérifiez s'il s'agit d'un multiple de
for q in range(Amax//p+1):
dp[p*q] = 0 #A[i]Définir tous les multiples de
if A[i] != A[i+1]:
ans += 1 #A[i]Compter si ne se chevauche pas
if dp[Amax] == 1: #Étant donné que la plage est terminée lors de la vérification des doublons, seul Amax est jugé séparément.
ans += 1
print(ans)
dp est dans l'état initial dp = [1 1 1 1 1 1 1 ...].
Par exemple Si A [0] = 3, le dp après une opération est dp = [0 1 1 0 1 1 0 ...].
Recommended Posts