Very difficult exam | forta

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 $D_{10} = \{1,2,5,10\}$.

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 \leq n \leq 100 \ 000$;
• $1 \leq$ numerele din șir $\leq 2 \cdot 10^9$;
• 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 \leq n \leq 10 \ 000$

Exemplul 1

forta.in

1
6
17 243 10 32 25 13

forta.out

32

Explicație

Cerința este $1$. $D_{17}={1,17}, D_{243}={1,3,9,27,81,243}, D_{10}={1,2,5,10}, D_{32}={1,2,4,8,16,32}, D_{25}={1,5,25}, D_{13}={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$.