프로그램 명: coci_iks
제한시간: 1 초
[요약] N개의 수가 주어진다.
당신은 주어진 수 중 두 수 A, B를 선택하고 A의 소인수 X를 정해서 A를 A/X로 바꾸고 B를 BX로 바꾸는 작업을 할 수 있다.
몇 번의 작업 후 N개의 수의 최대공약수로 가능한 최댓값을 구하고, 이 때 필요한 최소 작업의 수를 구한다.
1번째 예제에서
4 4 1 -> 4 2 2로 바꾸면 1번의 작업으로 최대공약수가 2가 된다
Mirkos great grandmother Katica is an avid mathematician. She likes to torment Mirko
with math games. This time she wrote down a sequence of numbers on a piece of
paper and told Mirko he may do the following:
- Choose any two numbers in the sequence (let's call them A i B) and a prime
number X such that A is divisible by X. After that, Mirko erases A and writes
in its place. In the end he erases B and writes in its place.
Mirko may perform this operation as many times he wants. His goal is to obtain the
maximum possible score, because he gets candy from his great grandmother if he does
so. The score for one sequence is the greatest common divisor of all the numbers
in the sequence.
He is not very good at this, and he likes his candy so he has asked you to help him.
Write a program that will calculate the maximum possible score. Since you are such a
nice guy, you should also print the smallest number of times Mirko must perform the
operation to obtain the maximum possible score.
입력
-
The first line of input contains one integer N, (1 ≤ N ≤ 100), number of elements in
the starting sequence.
-
The second line of input contains N positive integers smaller than or equal to 1 000 000, the sequence Katica gave to Mirko.
출력
The one and only line of output should contain two integers. The first integer is the
maximal possible score Mirko can obtain. The second integer is the smallest number of
operations Mirko needs to perform to obtain it.
입출력 예
입력
3
4 4 1
출력
2 1
입력
3
8 24 9
출력
12 3
입력
5
4 5 6 7 8
출력
2 2
출처:coci 2009-2010 contest4 3/6
번역:functionx
[질/답]
[제출 현황]
[푼 후(0)]