翻译自 https://zhuanlan.zhihu.com/p/85169630
字符串是 0-index．
周期引理：对于长为 \(n\) 的字符串 \(s\)，如果 \(p,q\) 均为 \(s\) 的周期，并且 \(p+q-\gcd(p,q)\leq n\)，那么 \(\gcd(p,q)\) 也是 \(s\) 的周期。
定义 \(s_p(i)=s_{i\bmod p},s_q(i)=s_{i\bmod p}\)，用生成函数来描述它，对于每个字符赋一个互不相等的权值作为系数，那么 \(s_p(x)=\frac{P(x)}{1-x^p},s_q(x)=\frac{Q(x)}{1-x^q}\)，其中 \(P(x)\) 是 \(p-1\) 次多项式，\(Q(x)\) 是 \(q-1\) 次多项式。
想要验证 \(s_p(x)\) 和 \(s_q(x)\) 完全相同，将两者作差得到 \(s_p(x)-s_q(x)=\frac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}\left(\frac{1-x^q}{1-x^{\gcd(p,q)}}P(x)+\frac{1-x^p}{1-x^{\gcd(p,q)}}Q(x)\right)=\frac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}H(x)\)，容易长除法验证 \((1-x^{\gcd(p,q)})\) 是 \((1-x^p)\) 和 \((1-x^q)\) 的因式。
右边两个都是 \(p+q-\gcd(p,q)-1\) 次多项式，而左边是常数项不为 \(0\) 的多项式。由于 \(p,q\) 均为 \(s\) 的周期那么 \(s_p(x)\) 和 \(s_q(x)\) 的 \([0,n-1]\) 的各项系数都相同，那么 \(s_p(x)-s_q(x)\) 最低 \(n\) 项系数均为 \(0\)，由于 \(p+q-\gcd(p,q)-1\leq n-1\)，如果 \(H(x)\) 不为 \(0\)，那么和 \(\frac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}\) 的常数项一乘就得到了 \(\leq n-1\) 项的不为 0 的系数。所以得出 \(H(x)=0\)．
于是我们知道 \(s_p(x)\) 与 \(s_q(x)\) 完全相同，而根据裴蜀定理，方程 \(p\cdot u+q\cdot v=\gcd(u,v)\) 存在整数解，从而有 \(s_i=s_p(i)=s_p(i+p\cdot u)=s_q(i+p\cdot u+q\cdot v)=s_q(i+\gcd(p,q))=s_{i+\gcd(p,q)}\)，周期引理得证。
标签：代数,frac,周期,cdot,多项式,引理,gcd From： https://www.cnblogs.com/do-while-true/p/17604431.html