> 设字符串s长度为l（l不超过1000000），如果s形如u^k，则称s具有周期数k
> 
> 引理一
> 设s具有周期数m,n，令h为m,n的最小公倍数，那么s具有周期数h
> 
> 引理二
> 对l进行素因子分解，那么不同的素数最多出现7个
> 
> 引理三
> 设l[0],l[1],...,l[r]为一个有限长的正整数数列，满足l[k+1]整除l[k]（0<=k<=r-1），
> l[0]=l,并且满足l[k+1]=l[k]的k最多不超过7个，
> 那么l[0]+l[1]+...+l[r]<=7*l，等号成立当且仅当r=6，l[0]=l[1]=...=l[6]
> 
> 算法
> 
> (1)对l进行素因子分解，得到 l=p[0]^t[0]*p[1]^t[1]*...*p[d]^t[d]
> 其中p[0]<p[1]<...<p[d]为素数，t[k]为正整数（0<=k<=d）
> 
> (2)设置初值k:=0，T:=1,执行下面循环，直到k=d+1结束
> {
> 如果t[k]>0且s具有周期数p[k]
>    记s:=s'^p[k]
>    令s:=s',T:=T*p[k]
>    t[k]:=t[k]-1
> 若条件不成立k:=k+1
> }
> T即为所求
> 
> 算法的正确性由引理一保证，根据引理一，s的所有可能的周期数都是最大周期数的约数，又由于最大周期数是l的约数，算法正确性得证。
> 
> 使用最朴素的方法检查“s是否具有周期数p[k]”，复杂度与length(s)成正比，
> 记为C*length(s),可以证明,该算法复杂度不超过7*C*l
> 
> 如果每次执行判断“s是否具有周期数p[k]”时，记下当前的length(s)，我们得到数列
> l[0],l[1],...,l[r]，
> 那么，算法的复杂度就是C*(l[0]+l[1]+...+l[r])。
> 借助引理二，可以证明，这个数列满足引理三的条件，因此得到最大复杂度7*C*l。
> 同时，我们还知道，最大复杂度在周期数是1的时候取得。

• Re:我想到的一个方法 (5) zmyd 2010-02-09 20:56:15
  • Re:我想到的一个方法 (10) acmer1183 2010-03-23 20:46:20