시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 144 48 35 49.296%

문제

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)의 서로 다른 값의 개수를 한 개의 정수로 출력한다. 답과 답 사이에는 공백이나 빈 줄은 허용되지 않는다.

예제 입력 1

2
4
6
3
3
6
8
0

예제 출력 1

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)의 값은 총 세 개이다.

W3sicHJvYmxlbV9pZCI6IjEwMjQ0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViNGU0IiwiZGVzY3JpcHRpb24iOiI8cD5uXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgMSZsZTtsbyZsZTtoaSZsZTtuXHVjNzU4IFx1YzgxNVx1Yzc1OFx1YzVlZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHVkNTY4XHVjMjE4Jm5ic3A7ZihsbyxoaSlcdWIyOTQgQTxzdWI+bG88XC9zdWI+XHViZDgwXHVkMTMwIEE8c3ViPmhpPFwvc3ViPlx1YWU0Y1x1YzljMCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjXHViNGU0XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuIGxvXHVjNjQwIGhpXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWFjMDAgXHVjNTQ0XHViMmNjJm5ic3A7XHVjNzc4XHViMzcxXHVjMmE0XHViNzdjXHViMjk0IFx1YzgxMFx1YzVkMCBcdWM4ZmNcdWM3NThcdWQ1NThcdWM3OTAuJm5ic3A7XHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCZuYnNwO2xvXHVjNjQwIGhpXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWFjZTBcdWI4MjRcdWQ1NzRcdWJjZmMgXHViNTRjLCBcdWMyMThcdWM1ZjQgQVx1YzVkMFx1YzExYyZuYnNwO1x1YWMwMVx1YWMwMSBcdWIyZTRcdWI5NzgmbmJzcDtmKGxvLGhpKVx1Yzc1OCBcdWFjMTJcdWM3NDAgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc4IFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4Jm5ic3A7biAoMSZsZTtuJmxlOzEwMCwwMDApXHVjNzc0IFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWM5MDRcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGMmbmJzcDthICgxJmxlO2EmbGU7MTAwKVx1YWMwMCBcdWMyMThcdWM1ZjRcdWM3NTgmbmJzcDtcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNWQwIDBcdWM3NzQgXHVjNzg1XHViODI1XHViNDE4XHViYTc0IFx1Yzc4NVx1YjgyNVx1Yzc3NCZuYnNwO1x1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1Yzc4NVx1YjgyNVx1YjQxYyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgZihsbyxoaSlcdWM3NTggXHVjMTFjXHViODVjJm5ic3A7XHViMmU0XHViOTc4Jm5ic3A7XHVhYzEyXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJmNVx1YWNmYyBcdWIyZjUgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc3NFx1YjA5OCBcdWJlNDggXHVjOTA0XHVjNzQwIFx1ZDVjOFx1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjYmRcdWM2YjAsPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+bG89MSwmbmJzcDtoaT0xLCZuYnNwO2YobG8saGkpPTQ8XC9saT5cclxuXHQ8bGk+bG89MSwgaGk9MiwgZihsbyxoaSk9MjxcL2xpPlxyXG5cdDxsaT5sbz0yLCBoaT0yLCBmKGxvLGhpKT02PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhYzAwXHViMmE1XHVkNTVjIGYobG8saGkpXHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWNkMWQgXHVjMTM4IFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMjQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR0NEcyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBzZXF1ZW5jZSBBIG9mIG4gbnVtYmVycywgZGVmaW5lIGYobG8saGkpLCAxJmxlO2xvJmxlO2hpJmxlO24sIGFzIHRoZSBHcmVhdGVzdCBDb21tb24gRGl2aXNvciBvZiBhbGwgdGhlIG51bWJlcnMgQWxvIHRocm91Z2ggQWhpLCBpbmNsdXNpdmUuIE5vdGUgdGhhdCBsbyBhbmQgaGkgYXJlIGluZGljZXMsIG5vdCBtZW1iZXJzIG9mIHRoZSBsaXN0LiBHaXZlbiBhbiBhcnJheSwgY29uc2lkZXJpbmcgYWxsIHBvc3NpYmxlIHZhbHVlcyBvZiBsbyBhbmQgaGksIGhvdyBtYW55IHVuaXF1ZSB2YWx1ZXMgb2YgZihsbyxoaSkgd2lsbCB0aGVyZSBiZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZWdpbiB3aXRoIGEgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgbiAoMSZsZTtuJmxlOzEwMCwwMDApIHJlcHJlc2VudGluZyB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZS4gVGhlIG5leHQgbiBsaW5lcyB3aWxsIGVhY2ggaGF2ZSBhbiBpbnRlZ2VyIGEgKDEmbGU7YSZsZTsxMDApLiBUaGVzZSBhcmUgdGhlIG51bWJlcnMgaW4gdGhlIHNlcXVlbmNlLCBpbiBzZXF1ZW5jZSBvcmRlci4gVGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdW5pcXVlIHZhbHVlcyBmKGxvLGhpKSBjYW4gaGF2ZSBmb3IgdGhlIGlucHV0IHNlcXVlbmNlLiBEbyBub3Qgb3V0cHV0IGFueSBzcGFjZXMsIGFuZCBkbyBub3QgcHJpbnQgYW55IGJsYW5rIGxpbmVzIGJldHdlZW4gYW5zd2Vycy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=