항공권 묶음의 공통 크기

문제

한 항공권 판매소는 출발편별로 남은 항공권을 묶음 상품으로 바꾸려 한다. 출발편은 모두 N개이며, i번째 출발편에는 항공권이 A_i장 남아 있다. 항공권 한 장을 나누거나 여러 출발편의 항공권을 섞는 일은 허용하지 않는다. 따라서 하나의 묶음에는 반드시 같은 출발편의 항공권만 들어가야 한다. 판매소는 관리하기 편하도록 모든 출발편에 같은 묶음 크기 k를 적용한다. 묶음 크기는 한 묶음에 들어가는 항공권의 장수이며, 2 이상의 정수여야 한다. 각 출발편의 항공권을 크기 k인 묶음으로 나누었을 때 남는 항공권이 한 장도 없어야 한다. 출발편마다 만들어지는 묶음의 개수는 달라도 되며, 어떤 출발편에서 묶음이 정확히 하나만 만들어져도 된다. 예를 들어 항공권이 12장 남은 출발편은 크기 2인 묶음 여섯 개나 크기 6인 묶음 두 개로 나눌 수 있다. 그러나 크기 5를 선택하면 항공권이 남으므로 그 크기는 사용할 수 없다. 다른 출발편이 함께 있다면 그 출발편에서도 같은 크기로 남김없이 나눌 수 있어야 한다. 판매소가 알고 싶은 것은 만들어지는 전체 묶음의 개수가 아니라, 선택할 수 있는 서로 다른 묶음 크기의 개수다. 두 크기의 정수 값이 다르면 서로 다른 선택으로 센다. 크기 1은 개별 판매에 해당하므로 어떤 경우에도 선택에 포함하지 않는다. 항공권이 한 장만 남은 출발편도 입력에 등장할 수 있으며, 이때도 모든 출발편에 같은 규칙을 적용한다. 가능한 묶음 크기가 하나도 없다면 개수는 0이다. 주어진 모든 출발편에 공통으로 적용할 수 있는 묶음 크기가 몇 개인지 구한다.

입력

첫째 줄에 출발편의 수 N이 주어진다. 둘째 줄에 N개의 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 50,000이며, 모든 i에 대해 1 ≤ A_i ≤ 1,000,000이다.

출력

모든 출발편의 항공권을 남김없이 나눌 수 있는 2 이상의 정수 묶음 크기의 개수를 한 줄에 출력한다. 가능한 크기가 없으면 0을 출력한다.

3
24 36 60

5

4
14 25 35 49

0

1
49

2

출처: Devin.KR 자체 제작