TopCoder

User's AC Ratio

81.4% (35/43)

Submission's AC Ratio

37.9% (94/248)

Tags

Description

KURORO製作公司是一作製造超級鑰匙的公司(茶)。
這次他們發明了一種非常酷炫的鑰匙,叫做kukukey。

而為什麼叫做kukukey呢?因為對應於這種鑰匙的鎖(kukulock)有一種特殊結構,一開始你需要用kukukey的n公分先插入鎖中,旋轉一圈後,再繼續插入n公分,再旋轉一圈,再繼續插入n公分....,總共會轉k次,也就是打開前總共會有k*n公分的鑰匙在鎖裡面,而我們稱這個n叫kuku 值,k則叫轉圈圈率。
因為鎖是鐵作的(意思是很硬XD),所以當你鑰匙深入p*n公分要旋轉時,前面部分的(p-1)*n公分也必須跟著旋轉,可想而知,如果要滿足這樣條件,從kukukey開始插入後每n公分就必須是長一樣的。

現在KURORO公司收到了一堆凹凸不平的鐵條,因為要把某些高出來的地方磨平很廢時又廢力,所以你想直接利用他上面凹凸不平的特性來製作這種鑰匙,因為當kuku值越大時,鑰匙的保護功用就越好(當然也可以賣的越貴),所以你希望盡可能的使kuku值大一點,對了因為鐵條是有方向性的,所以鐵條左端也會是鑰匙左端。

P.S.你不用擔心假如鐵條可以全部插到鑰匙孔裡時要怎麼旋轉,因為他們都會在右端加上塑膠柄,方便旋轉。

Input Format

第一行有一數k(1<=k<=100)代表要製作的鑰匙的轉圈圈率。
第二行包含一個很長的字串(1<=長度<=5000000),代表鐵條左到右每公分的凹凸情形(同樣的凹凸情形將會以同樣的字母來表示)。

Output Format

輸出一行一數代表最大的kuku值。

Sample Input 1

4
aabbaabbaabbaabbsurwdkgohowway

Sample Output 1

4

Sample Input 2

2
aabbaabbaabbaabbsurwdkgohowway

Sample Output 2

8

Hints

是說因為"kukukey"就是k=2,n=2的一把kukukey。

Problem Source

原TIOJ1531 / INFOR 22nd幹部考(prob H)。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10