← 返回题目列表

Codeforces · 1780/G

G. 美味甜点

中文机器翻译题面 查看原题

今天对于托尼奥厨师来说是重要的一天——一位审计员抵达了他的家乡杜王市。他也到达了托尼奥的餐厅并点了甜点。托尼奥还没有为这一转变做好准备。

如你所知,dessert是一串小写英文字母。托尼奥记得甜点的规则——长度为 $$$n$$$ 的字符串 $$$s$$$。如果 $$$t$$$ 作为子串在 $$$s$$$ 中出现的次数可以被 $$$t$$$ 的长度整除,那么任何甜点 $$$t$$$ 都是美味的。

现在托尼奥想知道 $$$s$$$ 的美味子串的数量。如果子字符串在字符串 $$$s$$$ 中出现多次,则必须考虑所有出现的情况。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 规则 $$$s$$$ 的长度。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$ — 规则。该规则仅由小写英文字母组成。

输出

在一行中打印 $$$s$$$ 的美味子字符串的数量。

示例

输入 #1

7
abacaba

输出 #1

11

输入 #2

8
abaababa

输出 #2

11

输入 #3

10
deadinside

输出 #3

12

输入#4

5
aaaaa

输出#4

12

注意

在第一个示例中,有许多美味的子字符串。其中 $$$7$$$ 是长度为 $$$1$$$ 的子串(因为任何数字都可以被 $$$1$$$ 整除)。考虑其他美味的子字符串:

- “ab”出现 $$$s$$$ $$$2$$$ 次,可被子字符串的长度整除。
- “ba”也出现了 $$$2$$$ 次。

因此,答案是$$$7 + 2 + 2 = 11$$$。

请注意,答案包括同时出现的“ab”和“ba”。