Rezolvare PBinfo #1950

Cerința

Se dă un şir format din N numere naturale nenule. Spunem că un număr e fericit dacă se poate scrie ca suma pătratelor a două numere naturale. Notăm cu K numărul numerelor fericite din şir şi cu P produsul acestora. Aflaţi numărul K precum şi două numere naturale care au suma pătratelor egală cu PE, unde E este un număr natural dat.

Date de intrare

Fișierul de intrare pxp.in conține pe prima linie numerele N şi E , iar pe a doua linie N numere naturale separate prin spațiu.

Date de ieșire

Fișierul de ieșire pxp.out va conține pe prima linie numărul K, reprezentând numărul numerelor fericite din şir iar pe a doua linie cele două numere care au suma pătratelor egală cu PE.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ E ≤ 3
• numerele din şir sunt mai mici decât 1.000.001 şi cel puţin un număr din şir este fericit
• 1 ≤ P ≤ 1036
• pentru a doua cerinţă se va afişa orice soluţie, fiecare test având soluţie
• pentru prima cerinţă se acordă 40p, iar pentru a doua 60p
• 30% din teste au P ≤ 1000000, iar alte 40% au P ≤ 1018
• 80% din teste au E=1, 10% au E=2 şi 10% au E=3

Exemplu:

pxp.in

5 1
11 2 13 7 5

pxp.out

3
3 11

Explicație

Avem N=5 şi E=1. În şir sunt 3 numere fericite, 2, 13 şi 5, deoarece 2=12+12 , 13=22+32 şi 5=12+22. Produsul lor este 130=32+112, deci două numere pentru care suma pătratelor este P1 sunt 3 şi 11.