시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 119 39 28 48.276%

문제

n개의 수로 이루어진 수열 A가 주어질 때, 1≤lo≤hi≤n의 정의역을 가지는 함수 f(lo,hi)는 Alo부터 Ahi까지 모든 원소들의 최대공약수로 정의된다. lo와 hi는 수열의 원소가 아닌 인덱스라는 점에 주의하자. 가능한 모든 lo와 hi의 값을 고려해볼 때, 수열 A에서 각각 다른 f(lo,hi)의 값은 몇 개나 존재할 수 있을까?

입력

입력은 여러 개의 테스트 케이스로 주어진다. 각각의 테스트 케이스는 수열의 길이인 한 개의 정수 n (1≤n≤100,000)이 포함된 줄로 시작하며, 다음 n개의 줄에는 각각 수열의 원소 a (1≤a≤100)가 수열의 순서대로 주어진다. n에 0이 입력되면 입력이 종료된다.

출력

각각의 테스트 케이스에 대해, 입력된 수열이 가질 수 있는 f(lo,hi)의 서로 다른 값의 개수를 한 개의 정수로 출력한다. 답과 답 사이에는 공백이나 빈 줄은 허용되지 않는다.

예제 입력

2
4
6
3
3
6
8
0

예제 출력

3
5

힌트

첫 번째 테스트 케이스의 경우,

  • lo=1, hi=1, f(lo,hi)=4
  • lo=1, hi=2, f(lo,hi)=2
  • lo=2, hi=2, f(lo,hi)=6

가능한 f(lo,hi)의 값은 총 세 개이다.