Problem 585: tablou

Enunț

Definim un număr natural “tablou” $X$ dacă și numai dacă:

$X$ este compus;
Există $A$ și $B$ numere naturale, astfel încât $A \times B = X, 2 \leq A \leq B \leq \frac{X}{2}$ cu proprietatea că există o matrice de forma dreptunghiulară cu lățimea $A$ si lungimea $B$ , astfel încât suma oricăror $A$ numere este pozitivă $(\geq 0)$ și există $B$ numere, astfel încât suma celor $B$ numere este divizibilă cu $X$ ;
Fiecare număr din coordonatele $(lin, col)$ va fi sub forma: $lin \times col \times (A - col + 1) \times (B - lin + 1)$ ;
Liniile vor fi numerotate de la $1$ la $A$ , iar coloanele vor fi numerotate de la $1$ la $B$ ;

De exemplu, 25 este un număr “tablou”, deoarece pot forma matricea de formă dreptunghiulară cu lățimea 5 și lungimea 5, arătând astfel:

Oricum am alege $5$ numere din matricea respectivă, suma celor 5 numere va fi pozitivă și există cele $5$ numere $40$ , $40$ , $40$ , $40$ și $40$ , ale căror sumă este $40 + 40 + 40 + 40 + 40 = 200 = 25 \times 8$ , deci suma a celor $5$ numere se divide cu $25$ .
Fiind dat numărul $N$ și pe următoarele $N$ linii câte un număr $X$ , să se afișeze $DA$ dacă $X$ este un număr “tablou”, respectiv $NU$ dacă $X$ nu este un număr “tablou”.

Cerință

Dat numărul natural $N$ și pe următoarele $N$ linii câte un număr $X$ , să se afișeze $DA$ dacă respectă proprietatea din enunț, respectiv $NU$ dacă nu respectă proprietatea din enunț.

Date de intrare

În fișierul tablou.in se va afla numărul $N$ pe prima linie, iar pe următoarele $N$ linii se va afla câte un număr natural $X$ .

Date de ieșire

În fișierul tablou.out se va afla mesajul $DA$ dacă numărul $X$ este un număr “tablou”, respectiv $NU$ dacă numărul $X$ nu este un număr “tablou”.

Restricții și precizări

$1 \leq N \leq 200.000$
$1 \leq X \leq 1.000.000$
Pentru 25 de puncte, $1 \leq N \leq 1.000$ și $1 \leq X \leq 100$
Pentru 4 puncte, fiecare X din fișierul de intrare nu este compus
1 nu se ia în considerare ca număr compus

Exemplu:

tablou.in

tablou.out

DA
NU
NU

Explicații:

25 este un număr “tablou”, deoarece există matricea de formă dreptunghiulară cu lățimea 5 și lungimea 5 care are proprietatea specificată din enunț.
13 nu este un număr ”tablou”, deoarece nu este compus.
18 nu este un număr “tablou”, deoarece nu există o matrice de formă dreptunghiulară care are proprietatea specificată în enunț.

tablou