设字符串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:我想到的一个方法 (917) zmyd 2010-02-09 20:55:47
  • Re:我想到的一个方法 (5) zmyd 2010-02-09 20:56:15
    • Re:我想到的一个方法 (10) acmer1183 2010-03-23 20:46:20
• Re:我想到的一个方法 (27) HJWAJ 2010-09-10 16:31:43