诈骗题。给了个模数但是答案根本达不到那个级别。
先提前给出一个引理，如果长度为 \(2n\) 的 \(s\) 有 \(s[1,n]=s[n+1,2n]\) 并且 \(s[1,m]=s[m+1,2m](m<n)\) 或者 \(s[1,2n-m+1]=s[m+1,2n](n<m<2n)\)，那么一定存在长度为 \(\gcd(n,m)\) 的循环节。很好证，因为其实就是证明划分单位，\(n,m\) 互质之后 \(s\) 的任何位都相等。而每次从第一个到第二个就是 \(i\) 和 \(i+m\) 相同，而 \(\bmod n\) 的环下面，一直 \(+m\) 走能遍历所有数，也就得证了。
这个引理的意义是什么呢？就是如果一个字符串存在循环节 \(m\)，它的某个前缀存在循环节 \(n\)，那么这个字符串一定存在循环节 \(\gcd (n,m)\)，前缀是自身依然成立，这种特殊情况引出字符串的任意循环节都是最小循环机的倍数。
我们考虑当前字符串的最小循环节。最小循环节为自身长度的串显然是好的。那么，最小循环节长度为 \(n\) 和 \(1\) 的情况可以直接特判掉，剩下情况而言：
假设最小循环节长度为 \(x\)，我们显然可以直接把第一位断开，变成一个字符和一个后缀。后缀很明显不会有循环节，因为假设其循环节长度为 \(m\)，因为长度恰好是 \(x\) 的倍数减一，所以不会是 \(x\) 的倍数。那么就能推出答案存在 \(\gcd(x,m)<x\) 的循环节，和假设矛盾。所以后一个显然不是循环的，那么显然可以分成两段解决。
分成两段解决就很方便了，只要枚举断开的位置然后判断两边是否都不循环即可。这就需要我们对前缀和后缀求最小循环节。
第一种方法：
对于所有前缀枚举其所有因子 \(d\)，预处理出来，因为调和级数总数是 \(n\log n\) 的。然后我当前要有大小为 \(d\) 的循环节，需要 \(i-d\) 前缀的也有。那么就是 \(i-d\) 的前缀的最小循环节需要是 \(d\) 的因数。然后还需要判断 \(s[1,d]\) 和 \(s[i-d+1,i]\) 是否相同，因为是和前缀判断，所以既可以用 Z 函数也可以用哈希。倒过来再做一遍，就可以解决了。注意这题也卡哈希和效率，写哈希的话还是要自然溢出+特殊 Base。
第二种方法则需要观察一些别的性质，如果一个串有循环节 \(x\)，那么等价于 \(x|n\) 并且 \(s[1,n-x]=s[x+1,n]\)。同时，如果一个串的 \(border\) 是 \(x\)，那么一定不存在小于 \(n-x\) 的循环节，因为如果有的话，它就会成为比 \(border\) 更长的合法串。
再还有，如果串有最小循环节 \(x\)，而 \(border>n-x\)，那么就有最左边和最右边的 \(n-border\) 串相等。两个拼起来，根据引理就有更小的循环节，这是不被允许的。
所以，串有最小循环节 \(x\)，等价于 \(x|n\) 且 \(border=n-x\)。
这样，我们就可以直接用 \(border\) \(O(1)\) 查找最小循环节。不需要枚举因数哈希什么的。总复杂度 \(O(n)\)。