问题
N개의 자연수들이 주어진다. 당신은 이 수들 중 두 수를 골라서 아래와 같은 작업을 할 수 있다.
작업) 두 수 A, B를 고른 후 A의 소인수 p를 선택해서, A와 B를 지우고 A/p와 B×p를 넣는다.
몇 번의 작업을 해서 N개의 수들의 최대공약수가 최대가 되게 할 때,
그 최댓값을 구하고 최소 몇 번의 작업을 해야 하는지 구하는 프로그램을 작성하여라.
输入
첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 100) 두 번째 줄에는 처음에 주어진 N개의 자연수들이 주어진다. 이 수들은 1,000,000 이하이다.
输出
최대공약수로 가능한 최댓값과 그 때 필요한 최소 작업 수를 출력한다.
示例 #1
3
4 4 1
2 1
示例 #2
3
8 24 9
12 3
示例 #3
5
4 5 6 7 8
2 2
提示
来源
COCI 2009/2010 contest 4 task 3 Iks
需要登录才能编写代码。