Rezolvare PBinfo #3433

Forța unui număr natural nenul X este egală cu numărul de divizori pozitivi ai lui X. De exemplu, numărul X = 10 are forţa 4, deoarece 10 are 4 divizori, mulțimea divizorilor fiind D10 = {1,2,5,10}.

Cerința

Scrieţi un program care, cunoscând un șir de n numere naturale nenule, rezolvă următoarele cerințe:

1. determină cel mai mic număr din șir care are forța maximă;
2. determină lungimea maximă a unei secvențe formată din numere cu aceeași forţă ce poate fi obținută prin rearanjarea convenabilă a elementelor din șir.

Date de intrare

Fișierul de intrare forta.in conține pe prima linie numărul c, care reprezintă cerința de rezolvat (1 sau 2), pe a doua linie un număr natural n, iar pe următoarea linie n numere naturale separate prin câte un spațiu, reprezentând elementele șirului.

Date de ieșire

Fișierul de ieșire forta.out va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerința c.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ numerele din șir ≤ 2.000.000.000
• O secvență este constituită dintr-un singur număr sau mai multe numere aflate pe poziții consecutive în șir. Lungimea unei secvențe este egală cu numărul de valori care o compun.
• Pentru prima cerință se acordă 50 de puncte, iar pentru cea de a doua cerință se acordă 40 de puncte.
• Pentru teste valorând 30 de puncte 1 ≤ n ≤ 10.000
• În concurs problema s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

forta.in

1
6
17 243 10 32 25 13

forta.out

32

Explicație

Cerința este 1. D17={1,17}, D243={1,3,9,27,81,243}, D10={1,2,5,10}, D32={1,2,4,8,16,32}, D25={1,5,25}, D13={1,13}. Deci cea mai mare forță este 6, iar numărul minim cu această forță este 32.

Exemplul 2

forta.in

2
8
121 10 14 25 49 9 25 15

forta.out

5

Explicație

Cerința este 2. O rearanjare a șirului ar putea fi (10 14 15)(121 25 49 9 25) astfel încât putem obține o secvență de lungime 3 de numere de forță 4 și o secvență de lungime 5 de numere de forță 3.