TopCoder

User's AC Ratio

81.0% (34/42)

Submission's AC Ratio

38.2% (95/249)

Tags

Description

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

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

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

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

Input Format

第一行有一數 $k (1 \le k \le 100)$ 代表要製作的鑰匙的轉圈圈率。
第二行包含一個很長的字串 $s (1 \le |s| \le 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)。
2024/07/12 Update: Reformatted & added $\LaTeX$ by FHVirus

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