승강장 표시선의 공통 간격

문제

지하철 차량기지에서는 여러 승강장의 바닥에 일정한 간격으로 안내 표시선을 붙이려 한다. 각 승강장에는 표시선을 붙일 직선 구간이 하나씩 있으며, 구간의 길이는 모두 양의 정수 센티미터로 측정되어 있다. 담당자는 작업 도구를 하나만 사용하기 위해 모든 구간에 같은 간격을 적용하기로 했다. 표시선 간격 d는 양의 정수 센티미터여야 한다. 길이가 L인 구간에는 시작점인 0센티미터 위치부터 d센티미터마다 표시선을 붙인다. 이때 마지막 표시선이 구간의 끝인 L센티미터 위치에 정확히 놓여야 한다. 따라서 구간의 끝에 도달하기 전에 간격을 줄이거나, 끝을 지나서 표시선을 붙이거나, 마지막 부분만 비워 두는 방식은 허용하지 않는다. 구간의 시작점과 끝점에 표시선을 붙이는 것은 항상 허용한다. 예를 들어 길이가 18센티미터인 구간에서는 3센티미터 간격을 사용할 수 있다. 표시선이 0, 3, 6, 9, 12, 15, 18 위치에 놓이기 때문이다. 그러나 다른 구간의 길이가 10센티미터라면 이 두 구간에 3센티미터 간격을 함께 적용할 수는 없다. 담당자가 알고 싶은 것은 가장 넓은 간격 하나가 아니라, 모든 구간에 공통으로 사용할 수 있는 간격의 종류 수다. 서로 다른 두 간격은 센티미터로 나타낸 정숫값이 다르면 다른 종류로 센다. 같은 길이의 구간이 여러 번 입력되어도 각 구간에 같은 규칙을 적용하며, 그 때문에 간격의 종류를 중복해서 세지는 않는다. 구간이 하나뿐인 경우에도 같은 규칙을 적용한다. 주어진 모든 구간을 끝까지 정확히 나눌 수 있는 양의 정수 간격이 몇 종류인지 구한다. 1센티미터 간격은 항상 사용할 수 있으므로 답은 반드시 1 이상이다.

입력

첫째 줄에 구간의 수 N이 주어진다. N은 1 이상 30,000 이하의 정수다.
둘째 줄에 각 구간의 길이 L_1, L_2, ..., L_N이 공백으로 구분되어 주어진다. 각 길이는 1 이상 1,000,000,000 이하의 정수다.

출력

모든 구간에 공통으로 사용할 수 있는 양의 정수 간격의 종류 수를 정수 하나로 출력한다.

3
30 42 66

4

4
14 25 39 52

1

1
49

3

출처: Devin.KR 자체 제작