prime

Time limit: 0.5s Memory limit: 72MB Input: prime.in Output: prime.out

Dornic să apară în probleme după mai mulți ani de așteptare, Micul Gates decide să joace următorul joc cu numere. Se consideră o mulțime de numere care la început este vidă.
Asupra acesteia se pot aplica următoarele tipuri de operații:

  • 1 x - Se adaugă numărul xx în mulțime;
  • 2 y - Se scot toate numerele divizibile cu (numărul prim) yy din mulțime;
  • 3 - Se dorește aflarea cardinalului mulțimii.

Cerința

Scrieți un program care determină rezultatele la operațiile de tipul 33.

Date de intrare

Pe prima linie a fișierului prime.in se află un număr NN. Pe următoarele NN linii se află câte o operație după structura explicată anterior.

Date de ieșire

Fișierul prime.out conține câte o linie cu valoarea determinată pentru fiecare cerință de tipul 33, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

  • Numărul de operații 3N31053 \leq N \leq 3 * 10^5, și există cel puțin o operație de tipul 33;
  • 2x21062 \leq x \leq 2 * 10^6;
  • 2y21062 \leq y \leq 2 * 10^6;
  • Pentru 3030 puncte, N103N \leq 10^3;
  • Toate numerele adaugate în mulțime prin operația de tipul 11 sunt diferite între ele.

Exemplu

prime.in

6
1 10
1 3
1 5
3
2 5
3

prime.out

3
1

Explicație

Inițial mulțimea este vidă. Primele 33 operații de tipul 11 adaugă pe rând 1010, 33, și 55.
Următoare linie reprezintă o cerință de tipul 33, la care răspunsul este 33, reprezentând cardinalul mulțimii {10,3,5}\{10, 3, 5\}.
Operația de pe linia următoare face să se scoată din mulțime numerele divizibile cu 55, adică {10,5}\{10, 5\}, deci la următoare operație de tip 33, mulțimea un element.

Log in or sign up to be able to send submissions!