P3499 [POI 2010] Divine Divisor

Source: POI 2010 Round I - [Divine Divisor](https://szkopul.edu.pl/problemset/problem/hOwg83Xw_OnTpfQ9SroS0OJA/site/?key=statement).

An integer $N > 1$ is given. We say that an integer $d > 1$ is a divisor of $N$ with multiplicity $k > 0$ ($k$ is integer) if $d^k \mid N$ and $d^{k+1}$ does not divide $N$. For example, the number $N = 18 = 16 \cdot 3$ has the following divisors: 2 with multiplicity 4, 3 with multiplicity 1, 4 with multiplicity 2, 6 with multiplicity 1, and so on. We say that a number $d$ is a *divine divisor* of the number $N$ if $d$ is a divisor of $N$ with multiplicity $k$ and $N$ has no divisors with multiplicities greater than $k$. For example, the sole divine divisor of 48 is 2 (with multiplicity 4), and the divine divisors of 6 are: 2, 3 and 6 (each with multiplicity 1). Your task is to determine the multiplicity of divine divisors of $N$ and the number of its divine divisors. ### Input ### Output ### Example For the input data: ``` 3 4 3 4 ``` the correct result is: ``` 4 1 ``` whereas for the input: ``` 1 6 ``` the correct result is: ``` 1 3 ``` ### Grading Should your program print out the correct multiplicity $k$ of a divine divisor of $N$, but fail to print in the second line the correct number $D$ of divine divisors of $N$ (or fail to print that number at all), it will be awarded 50% of the score for that particular test, scaled accordingly if it exceeds half the time limit.

The number $N$ is given on the standard input, though in a somewhat unusual way. The first line holds a single integer $n$ ($1 \le n \le 600$). The second line holds $n$ integers $a_i$ ($2 \le a_i \le 10^{18}$) separated by single spaces. These denote that $N = a_1 \cdot a_2 \cdot \dots \cdot a_n$.

The first line of the standard output should hold the maximum integer $k$ such that there exists a divisor $d$ of $N$ such that $d^k \mid N$. The second line should hold a single integer $D$ that is the number of (divine) divisors of $N$ with multiplicity $k$.

Should your program print out the correct multiplicity $k$ of a divine divisor of $N$, but fail to print in the second line the correct number $D$ of divine divisors of $N$ (or fail to print that number at all), it will be awarded 50% of the score for that particular test. Task author: Jakub Radoszewski.