시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB52022415446.246%

문제

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

W3sicHJvYmxlbV9pZCI6IjEwMjQ0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViNGU0IiwiZGVzY3JpcHRpb24iOiI8cD5uXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgMSZsZTtsbyZsZTtoaSZsZTtuXHVjNzU4IFx1YzgxNVx1Yzc1OFx1YzVlZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHVkNTY4XHVjMjE4IGYobG8saGkpXHViMjk0IEE8c3ViPmxvPFwvc3ViPlx1YmQ4MFx1ZDEzMCBBPHN1Yj5oaTxcL3N1Yj5cdWFlNGNcdWM5YzAgXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4Y1x1YjRlNFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBsb1x1YzY0MCBoaVx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWM3NzhcdWIzNzFcdWMyYTRcdWI3N2NcdWIyOTQgXHVjODEwXHVjNWQwIFx1YzhmY1x1Yzc1OFx1ZDU1OFx1Yzc5MC4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBsb1x1YzY0MCBoaVx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhY2UwXHViODI0XHVkNTc0XHViY2ZjIFx1YjU0YywgXHVjMjE4XHVjNWY0IEFcdWM1ZDBcdWMxMWMgXHVhYzAxXHVhYzAxIFx1YjJlNFx1Yjk3OCBmKGxvLGhpKVx1Yzc1OCBcdWFjMTJcdWM3NDAgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc4IFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IG4gKDEmbGU7biZsZTsxMDAsMDAwKVx1Yzc3NCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVjOTA0XHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3MCwgXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjIGEgKDEmbGU7YSZsZTsxMDApXHVhYzAwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNWQwIDBcdWM3NzQgXHVjNzg1XHViODI1XHViNDE4XHViYTc0IFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM3ODVcdWI4MjVcdWI0MWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0IGYobG8saGkpXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVhYzEyXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJmNVx1YWNmYyBcdWIyZjUgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc3NFx1YjA5OCBcdWJlNDggXHVjOTA0XHVjNzQwIFx1ZDVjOFx1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjYmRcdWM2YjAsPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+bG89MSwgaGk9MSwgZihsbyxoaSk9NDxcL2xpPlxyXG5cdDxsaT5sbz0xLCBoaT0yLCBmKGxvLGhpKT0yPFwvbGk+XHJcblx0PGxpPmxvPTIsIGhpPTIsIGYobG8saGkpPTY8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFjMDBcdWIyYTVcdWQ1NWMgZihsbyxoaSlcdWM3NTggXHVhYzEyXHVjNzQwIFx1Y2QxZCBcdWMxMzggXHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTAyNDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHQ0RzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHNlcXVlbmNlIEEgb2YgbiBudW1iZXJzLCBkZWZpbmUgZihsbyxoaSksIDEmbGU7bG8mbGU7aGkmbGU7biwgYXMgdGhlIEdyZWF0ZXN0IENvbW1vbiBEaXZpc29yIG9mIGFsbCB0aGUgbnVtYmVycyBBbG8gdGhyb3VnaCBBaGksIGluY2x1c2l2ZS4gTm90ZSB0aGF0IGxvIGFuZCBoaSBhcmUgaW5kaWNlcywgbm90IG1lbWJlcnMgb2YgdGhlIGxpc3QuIEdpdmVuIGFuIGFycmF5LCBjb25zaWRlcmluZyBhbGwgcG9zc2libGUgdmFsdWVzIG9mIGxvIGFuZCBoaSwgaG93IG1hbnkgdW5pcXVlIHZhbHVlcyBvZiBmKGxvLGhpKSB3aWxsIHRoZXJlIGJlPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciBuICgxJmxlO24mbGU7MTAwLDAwMCkgcmVwcmVzZW50aW5nIHRoZSBsZW5ndGggb2YgdGhlIHNlcXVlbmNlLiBUaGUgbmV4dCBuIGxpbmVzIHdpbGwgZWFjaCBoYXZlIGFuIGludGVnZXIgYSAoMSZsZTthJmxlOzEwMCkuIFRoZXNlIGFyZSB0aGUgbnVtYmVycyBpbiB0aGUgc2VxdWVuY2UsIGluIHNlcXVlbmNlIG9yZGVyLiBUaGUgaW5wdXQgd2lsbCBlbmQgd2l0aCBhIGxpbmUgd2l0aCBhIHNpbmdsZSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGludGVnZXIgZGVub3RpbmcgdGhlIG51bWJlciBvZiB1bmlxdWUgdmFsdWVzIGYobG8saGkpIGNhbiBoYXZlIGZvciB0aGUgaW5wdXQgc2VxdWVuY2UuIERvIG5vdCBvdXRwdXQgYW55IHNwYWNlcywgYW5kIGRvIG5vdCBwcmludCBhbnkgYmxhbmsgbGluZXMgYmV0d2VlbiBhbnN3ZXJzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

University > North American Invitational Programming Contest > NAIPC 2014 E번

  • 문제를 번역한 사람: expect017
  • 데이터를 추가한 사람: k1178k