好题:KMP应用,数学-Om Nom and Necklace

传送门:https://vjudge.net/problem/CodeForces-526D

题目大意：对于字符串的每一个前缀，询问是否能够看成 k + 1 个 A 和 k个B交替形成的字符串。

题目思路: KMP 找循环节 + 数学推导

着实被这个题解法秀到了.

首先想要答案存在，将 S = A + B。这个S肯定是这个前缀的一段循环节。

我们知道最小循环节为: 

我们知道：

由于n是定值，那么 就是求是否存在一个正整数 q :

所以接下来就判断区间中是否包含正整数，可以将左端点的值L向上取值，右端点的值R向下取值，判断 L <= R.