Postată de Clasa Intrare/ieșire Limită timp Limită memorie Sursa problemei Autor Dificultate
Candale Silviu (silviu) 11 greselile.in / greselile.out 0.7 secunde 64 MB / 32 MB Moisil++, 2016 Turcuman Vlad concurs

#1916 Catalin si greselile

Cerința

Îl cunoașteți, cred, pe Cătălin, fan-ul numărul 1 al greșelilor. Ei bine, în teza la mate, Cătălin a făcut N greșeli. Presupunând, prin reducere la absurd, că el corectează o greșeală i, poate alege să corecteze o singură greșeală j, cu proprietatea 1<j<i şi i%j=0. El știe că, dacă face această alegere poate să continue din greșeala j, după aceeași regulă și nu mai poate reveni la o greșeala anterioară.

Cătălin alege T greșeli G[1] G[2] … G[T] și dorește să știe, pentru fiecare G[i], numărul maxim de greșeli pe care le poate corecta dacă începe rezolvând-o pe aceasta.

Date de intrare

Fișierul de intrare greselile.in conține pe prima linie două numere N și T unde N este numărul de greșeli și T numărul de întrebări. Următoarele T linii conțin câte un număr natural nenul reprezentând greșeala de la care Cătălin vrea să pornească corectarea.

Date de ieșire

Fișierul de ieșire greselile.out va conține fiecare linie i un singur număr natural reprezentând numărul maxim de greșeli care pot fi corectate dacă ar începe Cătălin cu greșeala G[i].

Restricții și precizări

  • 1 ≤ N, T ≤ 1.000.000

Exemplu

greselile.in

10 9
3
4
6
2
5
7
8
9
10

greselile.out

1
2
2
1
1
1
3
2
2

Explicație

Corectează doar 3 deoarece numărul nu are divizori proprii.
Pornind cu 4 el va corecta 4 şi 2.
Pornind cu 6 el va corecta 6 şi 3 sau 6 și 2, maximul fiind de 2 greşeli corectate.
ș.a.m.d.

Categorii

Pentru a trimite soluții trebuie să fiți autentificat.

Autentificare