Cerința

Gigel a descoperit un nou joc. Jocul are n nivele și la fiecare nivel îți dă câte un număr natural x. Pentru a trece nivelul trebuie să calculezi câți divizori are numărul x. Scrieți un program care să permită terminarea jocului prin trecerea celor n nivele în ordinea în care sunt date.

Date de intrare

Fișierul de intrare joc2020.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire joc2020.out va conține pe prima linie n numere, fiecare reprezentând numărul de divizori ai numărului corespunzător din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 500.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici sau egale cu 1.000.000
• pentru 50 de puncte n ≤ 10.000

Exemplu

joc2020.in

7
30 5 44 210 1 35 30030

joc2020.out

8 2 6 16 1 4 64 

Explicație

Numerele date au divizori astfel: 30 are 8 divizori, 5 are 2 divizori, etc.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("joc2020.in");
ofstream cout("joc2020.out");

bool c[1000001];
int divi[100001], ind = 0;
int rez[500001];

int main()
{
    c[0] = c[1] = 1;
    for(int i = 2; i <= 1000; ++i)
        if(c[i] == 0)
            for(int j = 2; i * j <= 1000000; ++j)
                c[i * j] = 1;

    for(int i = 1; i <= 1000000; ++i)
        if(c[i] == 0)
            divi[++ind] = i;

    int n;
    cin >> n;
    int x;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        int nrdiv = 1;
        int d = 1;
        while(x > 1){
            int p = 0;
            while(x % divi[d] == 0)
                x /= divi[d], p++;
            d++;
            nrdiv *= (p + 1);
            if(divi[d] * divi[d] > x){
                if(x != 1){
                    nrdiv *= 2;
                    break;
                }
            }
        }
        rez[i] = nrdiv;
    }

    for(int i = 1; i <= n; ++i)
        cout << rez[i] << ' ';

    return 0;
}