학원 학습지 묶음 규격

문제

한 학원에서는 수업에 사용할 학습지를 종류별로 인쇄한 뒤 작은 묶음으로 포장한다. 학습지의 종류는 N가지이며, i번째 종류는 Aᵢ장 준비되어 있다. 모든 학습지는 포장해야 하고, 한 묶음에는 한 종류의 학습지만 들어갈 수 있다. 서로 다른 종류의 학습지를 섞어서 한 묶음을 만들 수는 없다. 담당자는 포장 작업을 단순하게 하기 위해 모든 묶음에 들어가는 학습지의 장수를 하나의 정수 K로 통일하려 한다. 포장 재료를 아끼기 위해 K는 2 이상이어야 한다. 어떤 종류의 학습지를 포장하든 정확히 K장씩 묶어야 하므로, 마지막 묶음에만 더 적은 장수를 넣는 것은 허용되지 않는다. 남는 학습지를 버리거나 다른 날의 포장 작업으로 넘기는 것도 허용되지 않는다. 예를 들어 하나의 규격 K를 정했다면, 첫 번째 종류부터 마지막 종류까지 각각의 학습지를 그 규격으로 빠짐없이 나눌 수 있어야 한다. 종류마다 만들어지는 묶음의 개수는 달라도 된다. 어떤 종류가 정확히 한 묶음으로 포장되는 것도 가능하다. 모든 종류의 학습지는 적어도 한 장씩 준비되어 있으므로, 준비된 장수가 K보다 작은 종류가 있다면 그 K는 사용할 수 없다. 학원에서는 가능한 규격을 먼저 모두 검토한 뒤 포장 재료를 주문하려 한다. 이때 같은 K는 한 가지 규격으로 세며, 묶음을 만드는 순서나 완성된 묶음을 놓는 순서는 서로 다른 규격으로 세지 않는다. 각 종류의 학습지 장수가 주어질 때, 위 조건을 만족하는 정수 K가 몇 개인지 구하는 프로그램을 작성한다. 가능한 규격이 하나도 없다면 0을 출력한다.

입력

첫째 줄에 학습지 종류의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 30,000이다.
둘째 줄에 각 종류의 학습지 장수를 나타내는 정수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 1 ≤ Aᵢ ≤ 1,000,000,000이다.

출력

모든 종류의 학습지를 남김없이 포장할 수 있는 정수 규격 K ≥ 2의 개수를 한 줄에 출력한다. 가능한 규격이 없으면 0을 출력한다.

3
24 36 60

5

3
14 25 39

0

1
49

2

출처: Devin.KR 자체 제작