항공권 묶음의 크기

문제

한 항공권 판매소는 하루 동안 발급한 항공권을 노선별로 나누어 보관한다. 오늘 항공권을 발급한 노선은 N개이며, i번째 노선의 항공권 수는 A_i장이다. 모든 항공권은 이미 노선별로 구분되어 있고, 서로 다른 노선의 항공권을 하나의 묶음에 넣을 수는 없다. 판매소는 보관함을 정리하기 위해 모든 노선에 똑같은 묶음 크기를 적용하려고 한다. 묶음 크기 d를 선택하면 각 노선의 항공권을 정확히 d장씩 나눈다. 이때 어느 노선에서도 남는 항공권이 없어야 하며, 모든 묶음에 들어가는 항공권 수가 같아야 한다. 노선마다 만들어지는 묶음의 개수는 달라도 된다. 예를 들어 어떤 노선의 항공권이 12장이면 묶음 크기 3을 적용하여 네 묶음을 만들 수 있다. 그러나 묶음 크기 5를 적용하면 항공권이 남으므로 그 크기는 선택할 수 없다. 판매소는 한 장짜리 묶음은 정리 효과가 없다고 생각한다. 따라서 묶음 크기 d는 2 이상의 정수여야 한다. 어떤 노선에서 묶음이 하나만 만들어져도 괜찮으며, 선택한 크기는 모든 노선에서 동시에 사용할 수 있어야 한다. 항공권을 추가하거나 버리는 일은 허용하지 않는다. 노선의 순서를 바꾸어도 사용할 수 있는 크기는 달라지지 않는다. 판매소가 선택할 수 있는 서로 다른 묶음 크기의 개수를 구하는 프로그램을 작성한다. 묶음 크기가 다르면 서로 다른 선택으로 세고, 같은 크기로 묶음을 만드는 순서나 보관함에 넣는 순서는 따로 세지 않는다. 사용할 수 있는 크기가 하나도 없으면 개수는 0이다.

입력

첫째 줄에 노선 수 N이 주어진다.
둘째 줄에 N개의 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 100,000이며, 모든 i에 대하여 1 ≤ A_i ≤ 999이다. 입력에 등장하는 모든 수는 정수이다.

출력

모든 노선에 공통으로 적용할 수 있는 2 이상의 정수 묶음 크기의 개수를 정수 하나로 출력한다. 가능한 크기가 없으면 0을 출력한다.

3
12 18 30

3

4
8 12 20 28

2

3
7 10 13

0

출처: Devin.KR 자체 제작