Cerința

Se dau n perechi de numere naturale, x şi k. Verificaţi pentru fiecare număr x dacă este produs de k numere prime distincte.

Date de intrare

Fișierul de intrare eratostene7.in conține pe prima linie numărul n, iar pe următoarele n linii câte o pereche de numere x şi k, separate prin spaţiu.

Date de ieșire

Fișierul de ieșire eratostene7.out va conține pe primele n linii cuvântul DA sau NU corespunzător celei de-a n-a perechi din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ x ≤ 1.000.000
• 1 ≤ k ≤ 100

Exemplu

eratostene7.in

3
20 3
30 3
49 2

eratostene7.out

NU
DA
NU

Explicație

Numărul 20 nu este produs de 3 numere prime distincte, 30=2•3•5 este produs de trei numere prime distincte, 49 nu este produs de 2 numere prime distincte.

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){
    int n;
    eratostene();
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int x, y;
        cin >> x >> y;
        if(desc(x) == y)
            cout << "DA" << '\n';
        else
            cout << "NU" << '\n';
    }
    return 0;
}