#P18175. Counting Strings
Counting Strings
Counting Strings
给定一个长度为 的字符串 ,下标从 1 开始。
称非空字符串 被 提及,当且仅当存在整数 ,使得
$$1\le l\le r\le n,\qquad\gcd(l,r)=1,\qquad s[l..r]=t.$$其中 是从第 个字符到第 个字符组成的连续子串。
求所有被提及的不同非空字符串的长度之和。
一个字符串只要有一次出现的两端下标互素就符合条件,即使它还在其他不互素的位置出现,也只计入一次。这里按字符串内容去重,不按出现位置计数。
输入格式
第一行一个整数 ,满足 。
第二行一个长度恰为 的字符串 ,仅包含小写英文字母。
输出格式
输出一个整数,表示所求的长度之和。答案不取模,需要使用 64 位整数。
样例
输入:
4
abca
输出:
14
被提及的不同字符串为 a、ab、abc、abca、bc、ca,长度之和为 。