自动搬运

查看原文

来自洛谷，原作者为

	Yajnun **

搬运于2025-08-24 21:50:29，当前版本为作者最后更新于2019-01-25 21:17:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

若小串$a$的首位在$c\left [ x \right ]$位出现 ，则 $a\left [ i\right ]$在$c\left [ x+i \right ]$位出现。若两者相同，$a(i+x)+b=a*x+a*i+b$，令$t=a*i+b$，则在模$n$意义下

若$a\left [ i \right ]=0$，$-t\leqslant ax\leqslant p-t-1$，令$l=-t,r=p-t-1 (mod~ n)$

若$a\left [ i \right ]=1$，$p-t\leqslant ax\leqslant -t-1$，令$l=p-t,r=-t-1 (mod~ n)$

若$l\leqslant r$，$a*x\in S=[l,r]$，否则$a*x\in S=[0,l]\cup [r,n-1]$

通过枚举$i$可得到这样一组约束条件，通过对其取交集可求出$a*x$的范围。对前者可直接求出，对后者不如转换成其补集的并集的补集。因为$a$与$n$互质，所以在x可以任意取的情况下，$a*x$与$[0,n-1]$是一一对应的关系，$\left |S \right |$即为$a*x$的所有取值。

因为实际上$x$不能完全取完$1$到$n$的值，所以对于应再枚举有哪些$x\in[n-m+1,n-1],a*x\in S$，用总数减去这个值即为答案。