시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB67420213531.765%

문제

어떤 길이가 양의 정수인 수열은 잘생긴 GCD 라는 값을 가질 수 있다. 잘생긴 GCD란 그 수열의 모든 원소들의 최대공약수에 수열의 길이를 곱한 값으로 정의된다.

당신의 임무는 수열이 주어질 때(a1, ... , an) 그 수열의 연속된 부분수열들의 잘생긴 GCD 중 가장 큰 값을 구하는 것이다.

입력

입력은 여러개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수를 의미하는 T 가 주어진다. 각 각의 테스트 케이스들은 두 줄로 구성되는데,  첫 줄은 수열의 크기 n ( 1 ≤ n ≤ 100 000 )이 주어진다. 두 번째 줄은 수열 a1, a2, ... , an 이 하나의 공백을 사이에 두고 주어지고 수열의 값은 1 이상 1,000,000,000,000 이하의 값을 가진다.

출력

각 각의 테스트 케이스에서 주어지는 수열의 연속 된 부분수열 중 잘생긴 GCD의 값이 가장 큰 수열의 잘생긴 GCD를 출력한다.

예제 입력 1

1
5
30 60 20 20 20

예제 출력 1

80
W3sicHJvYmxlbV9pZCI6Ijk1MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OThcdWMwZGRcdWFlMzQgR0NEIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzggXHVjMjE4XHVjNWY0XHVjNzQwIFx1Yzc5OFx1YzBkZFx1YWUzNCBHQ0QgXHViNzdjXHViMjk0IFx1YWMxMlx1Yzc0NCBcdWFjMDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzk4XHVjMGRkXHVhZTM0IEdDRFx1Yjc4MCBcdWFkZjggXHVjMjE4XHVjNWY0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhY2YxXHVkNTVjIFx1YWMxMlx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc1OCBcdWM3ODRcdWJiMzRcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMoYTxzdWI+MTxcL3N1Yj4sIC4uLiAsIGE8c3ViPm48XC9zdWI+KSBcdWFkZjggXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWI0ZTRcdWM3NTggXHVjNzk4XHVjMGRkXHVhZTM0IEdDRCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFQgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViNGU0XHVjNzQwIFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHViMjk0XHViMzcwLCAmbmJzcDtcdWNjYWIgXHVjOTA0XHVjNzQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgbiZuYnNwOyggMSAmbGU7IG4gJmxlOyAxMDAgMDAwIClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWMyMThcdWM1ZjQgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4gLCBhPHN1Yj5uPFwvc3ViPiBcdWM3NzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzEyXHVjNzQwIDEgXHVjNzc0XHVjMGMxIDEsMDAwLDAwMCwwMDAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhYzAwXHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzVmMFx1YzE4ZCBcdWI0MWMgXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0IFx1YzkxMSBcdWM3OThcdWMwZGRcdWFlMzQgR0NEXHVjNzU4IFx1YWMxMlx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM3OThcdWMwZGRcdWFlMzQgR0NEXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NTM3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFnaWNhbCBHQ0QiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBNYWdpY2FsIEdDRCBvZiBhIG5vbmVtcHR5IHNlcXVlbmNlIG9mIHBvc2l0aXZlIGludGVnZXJzIGlzIGRlZmluZWQgYXMgdGhlIHByb2R1Y3Qgb2YgaXRzIGxlbmd0aCBhbmQgdGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIGFsbCBpdHMgZWxlbWVudHMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgc2VxdWVuY2UgKGE8c3ViPjE8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+KSwgZmluZCB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBNYWdpY2FsIEdDRCBvZiBpdHMgY29ubmVjdGVkIHN1YnNlcXVlbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQuIFRoZSBkZXNjcmlwdGlvbnMgb2YgdGhlIHRlc3QgY2FzZXMgZm9sbG93OjxcL3A+XHJcblxyXG48cD5UaGUgZGVzY3JpcHRpb24gb2YgZWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBuLCAxICZsZTsgbiAmbGU7IDEwMCAwMDAuIFRoZSBuZXh0IGxpbmUgY29udGFpbnMgdGhlIHNlcXVlbmNlIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPiwgMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjEyPFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlcjogdGhlIGxhcmdlc3QgTWFnaWNhbCBHQ0Qgb2YgYSBjb25uZWN0ZWQgc3Vic2VxdWVuY2Ugb2YgdGhlIGlucHV0IHNlcXVlbmNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Central European Regional Contest > CERC 2013 C번