시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 92 | 28 | 25 | 33.333% |
N개의 정수로 이루어진 배열 ai가 주어져 있다. 이 배열에 다음과 같은 두 종류의 연산을 수행하려고 한다.
1번 연산은 최대 1번만 수행할 수 있고, 2번 연산은 각 수에 대해 최대 1번만 수행할 수 있다.
1번 연산의 비용은 m×A, 2번 연산의 비용은 1번에 B이다. 주어진 배열의 GCD를 1보다 크게 만들려고 할 때 필요한 최소 비용을 구하는 프로그램을 작성하시오.
첫째 줄에 N, A, B가 주어진다. (1 ≤ N ≤ 1,000,000; 1 ≤ A, B ≤ 109)
둘째 줄에는 배열에 들어있는 수 a1, a2, ..., aN이 주어진다. (2 ≤ ai ≤ 109)
첫째 줄에 배열의 GCD를 1보다 크게 만드는 최소 비용을 출력한다.
3 1 4 4 2 3
1
5 3 2 5 17 13 5 6
8
8 3 4 3 7 5 4 3 12 9 4
13
예제 1은 1번 연산으로 3번째 수를 삭제하면 최소 비용이다.
예제 2는 1번 연산으로 2~3번째 수를 삭제, 2번 연산으로 5번째 수를 1 줄이면 최소 비용이다.