[POI2010] NAJ-Divine Divisor
题目描述
An integer ![](http://main.edu.pl/images/OI17/naj-en-tex.1.png) is given.
We say that an integer ![](http://main.edu.pl/images/OI17/naj-en-tex.2.png) is a divisor of ![](http://main.edu.pl/images/OI17/naj-en-tex.3.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.4.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.5.png) is integer) if ![](http://main.edu.pl/images/OI17/naj-en-tex.6.png) and ![](http://main.edu.pl/images/OI17/naj-en-tex.7.png) does not divide ![](http://main.edu.pl/images/OI17/naj-en-tex.8.png).
For example, the number ![](http://main.edu.pl/images/OI17/naj-en-tex.9.png) 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 ![](http://main.edu.pl/images/OI17/naj-en-tex.10.png) is a divine divisor of the number ![](http://main.edu.pl/images/OI17/naj-en-tex.11.png) if ![](http://main.edu.pl/images/OI17/naj-en-tex.12.png) is a divisor of ![](http://main.edu.pl/images/OI17/naj-en-tex.13.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.14.png) and ![](http://main.edu.pl/images/OI17/naj-en-tex.15.png) has no divisors with multiplicities greater than ![](http://main.edu.pl/images/OI17/naj-en-tex.16.png).
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 ![](http://main.edu.pl/images/OI17/naj-en-tex.17.png) and the number of its divine divisors.
给定一个正整数 $m$ 以及长度为 $m$ 的正整数序列 $a$ ,同时给出 $n = \prod_{i=1}^{m}{a_i}$。你需要找出一个最大的 $k$ 使得存在一个 $d$ , $d > 1$ 并且 $d^k | n$。求这个最大的 $k$ 以及在 $k$ 最大的情况下有多少个 $d$ 满足条件。
输入输出格式
输入格式
The number ![](http://main.edu.pl/images/OI17/naj-en-tex.18.png) is given on the standard input, though in a somewhat unusual way.
The first line holds a single integer ![](http://main.edu.pl/images/OI17/naj-en-tex.19.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.20.png)).
The second line holds ![](http://main.edu.pl/images/OI17/naj-en-tex.21.png) integers ![](http://main.edu.pl/images/OI17/naj-en-tex.22.png) (![](http://main.edu.pl/images/OI17/naj-en-tex.23.png)) separated by single spaces.
These denote that ![](http://main.edu.pl/images/OI17/naj-en-tex.24.png).
输出格式
The first line of the standard output should hold the maximum integer ![](http://main.edu.pl/images/OI17/naj-en-tex.25.png) such that there exists a divisor ![](http://main.edu.pl/images/OI17/naj-en-tex.26.png) of ![](http://main.edu.pl/images/OI17/naj-en-tex.27.png) such that ![](http://main.edu.pl/images/OI17/naj-en-tex.28.png).
The second line should hold a single integer ![](http://main.edu.pl/images/OI17/naj-en-tex.29.png) that is the number of (divine) divisors of ![](http://main.edu.pl/images/OI17/naj-en-tex.30.png) with multiplicity ![](http://main.edu.pl/images/OI17/naj-en-tex.31.png).
输入输出样例
输入样例 #1
3
4 3 4
输出样例 #1
4
1
说明
$1\le m\le 600$,且$\forall 1\le i\le m$,有$1\le a_i\le 10^{18}$