CF1780G.Delicious Dessert

今天对厨师 Tonio 来说是重要的一天——一位审计员来到了他的家乡 Morioh。他还来到了 Tonio 的餐厅并点了甜点。Tonio 对这一突发事件毫无准备。

如你所知，甜点是由小写英文字母组成的字符串。Tonio 记得甜点的规则——给定一个长度为 $n$ 的字符串 $s$。如果某个甜点 $t$ 作为子串在 $s$ 中出现的次数能够被 $t$ 的长度整除，那么这个甜点 $t$ 就是美味的。

现在 Tonio 想知道 $s$ 中有多少个美味的子串。如果某个子串在字符串 $s$ 中出现了多次，则每一次出现都要计入答案。

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）——规则字符串 $s$ 的长度。

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

输出一行，表示 $s$ 中美味子串的数量。

在第一个样例中，有许多美味的子串。长度为 $1$ 的子串有 $7$ 个（因为任何数都能被 $1$ 整除）。再考虑其他美味的子串：

• "ab" 在 $s$ 中出现了 $2$ 次，可以被子串长度整除。
• "ba" 也出现了 $2$ 次。

因此，答案为 $7 + 2 + 2 = 11$。

注意，答案包含了 "ab" 和 "ba" 的每一次出现。

由 ChatGPT 4.1 翻译