Cerința

Se dau n numere naturale. Pentru fiecare număr aflaţi câţi divizori liberi de pătrate are acesta.

Date de intrare

Fișierul de intrare eratostene4.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 eratostene4.out va conține pe prima linie, pentru fiecare număr din fişierul de intrare, numărul divizorilor liberi de pătrate ai acestuia.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000
• un număr natural se numeşte liber de pătrate dacă nu se divide cu pătratul unui număr prim

Exemplu

eratostene4.in

3
20 8 5

eratostene4.out

4 2 2

Explicație

Divizorii lui 20, liberi de pătrate, sunt: 1, 2, 5, 10.
Divizorii lui 8, liberi de pătrate, sunt: 1, 2.
Divizorii lui 5, liberi de pătrate, sunt: 1, 5.

#include <bits/stdc++.h>

using namespace std;

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

int p[500001], P;
bitset<10000000> e;

void eratostene(){
    e[0] = e[1] = 1;
    for(int i = 2; i * i <= 100000; ++i)
        for(int j = i * i; j <= 100000; j += i)
            e[j] = 1;
    for(int i = 1; i <= 100000; ++i)
        if(!e[i])
            p[++P] = i;
}

int desc(int n){
    int d = 1;
    int cnt=0;
    while(n > 1){
        int pi = 0;
        while(n % p[d] == 0)
            n/=p[d], pi++;
        if(pi)
            cnt++;
        d++;
        if(n > 1 && p[d] * p[d] > n){
            cnt++;
            break;
        }
    }
    return cnt;
}

int main(){
    int n;
    eratostene();
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        cout << (1<<desc(x)) <<' ';
    }
    return 0;
}