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

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

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

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

我们知道最小循环节为: $min\_cir=n-next[n]$

$设 S = q * min\_cir$

$n = k * |S|+|A|=k * (q*min\_cir)+|A|$

我们知道： $0\leq |A|\leq|S| = q*min\_cir$

$n = k * |S|+|A|=k * (q*min\_cir)+[0,q*min\_cir]$

$=[k * (q*min\_cir),(k + 1) * (q*min\_cir)]$

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

$[\frac{n}{(k + 1 )*min\_cir} , \frac{n}{ k *min\_cir} ]$

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