TopCoder

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

71.4% (30/42)

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

Sample Input#1:
4
aabbaabbaabbaabbsurwdkgohowway

Sample Input#2:
2
aabbaabbaabbaabbsurwdkgohowway

Sample Output

Sample Output#1:
4

Sample Output#2:
8

Hints

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

Problem Source

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

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144