标准模板

将字符串映射到数，以便实现 的字符串判重。

我们自己取一个滴数 , 膜数，

那么 。

就是整个字符串的哈希值。

为了避免哈希冲突（及两个不同的字符串哈希值相同）的情况，我们一般将 选为质数。

如果只需判重，可以同时计算几个不同底数、模数的哈希值，防止哈希碰撞。

区间的哈希

那么

例题

#10035. 「一本通 2.1 练习 1」Power Strings

求字符串的最小循环节。

字符串以 为循环节等价于

画图可知显然。

#10038. 「一本通 2.1 练习 4」A Horrible Poem

给定只含小写字母的字符串，求区间的最小循环节。

如果这个区间的最大循环节是 ,

那么 ，且 一定整除区间内的各个字母出现次数

每次询问区间内各字母个数的最大公约数。

能过

#2427. 「POI2010」珍珠项链 Beads

正解就是暴力。记住调和级数

小细节：此题需要记录正着反着两种哈希值。

做法 ：

利用线性筛求出每个数的最小质因子。

如果 是循环节，那么显然 （）也是循环节。

故 从大到小枚举因子即可。

用于获取 的所有质因子，试着去除 ， 就可以枚举到所有质因子。

（实际上没有枚举所有，但是由于上述性质，可以得到答案所需的那个最小因子。）