CCEX Suceava 2023 - clasa a VI-a | Produs

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s
Memory limit: 8MB
Input: produs.in
Output: produs.out

Andrei este un elev pasionat la informatică. Astăzi a învățat despre cel mai mare divizor comun a două numere și are ca temă să afle câte perechi de numere pp și qq (pqp \leq q) prime între ele există, astfel încât pq=np \cdot q = n. Ajutați-l pe acesta să afle răspunsul cu ajutorul unui program eficient.

Cerinţă

Se dă tt și tt numere naturale nn. Pentru fiecare număr nn, să se afișeze câte perechi pp și qq există cu proprietatea din enunț.

Date de intrare

Fișierul de intrare produs.in conține pe prima linie numărul tt. Pe a doua linie se vor afla tt numere naturale.

Date de ieşire

Fișierul de ieșire produs.out conține tt linii, pe linia ii aflându-se răspunsul de la al ii-lea număr.

Restricţii și precizări

  • 1t41051 \leq t \leq 4 \cdot 10^5
  • 1n41061 \leq n \leq 4 \cdot 10^6
  • (p,q)(p, q) și (q,p)(q, p) sunt perechi diferite.
  • Pentru 4040 de puncte n105n \leq 10^5 și testele sunt generate aleatoriu.
  • Pentru 8080 de puncte n106n \leq 10^6.

Exemplu

produs.in

4
1 6 9 7

produs.out

0
4
2
2

Explicație

Pentru 66, cele 44 perechi sunt (1,6)(1, 6), (6,1)(6, 1), (2,3)(2, 3), (3,2)(3, 2).

Contest info

Official contest

Start time: 1700226900000

Total duration: 2h0m0s

Status: Ended

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