Floyed判环/龟兔算法

求[(5+2√6)^{2^x+1}] mod p 的值，其中 0 ≤ x < 2³², p 是个质数，p ≤ 46337 .（这里介绍的是一种暴力的做法）

(5+2√6)^{2^n+1} = a_n + b_n·√6 ----©,

(5-2√6)^{2^n+1} = a_n - b_n·√6 ;

所以(5+2√6)^{2^n+1} + (5-2√6)^{2^n+1} = 2a_n ;

因为5-2√6<1 , 所以[(5+2√6)^{2^x+1} ] = 2a_n- 1 ;

然后(5+2√6)^{2^x+1} = (5+2√6) ·(a_n-1 + b_n-1·√6) -----®;

由C,R得:

a_n=5a_n-1+ 12b_n-1 ,

b_n=2a_n-1+ 5b_n-1 ;

所以我们要求的就是 a_{2^x+1 ;}

但是即使用矩阵快速幂，复杂度为O(x) , 所以并卵；同时矩阵并不能用 欧拉定理 进行优化。

所以波老师就大胆的猜测对于这个问题 a_n mod p 的 循环节不会很大，所以之后就是暴力找循环节了。

floyed判圈算法描述:

我们令周期为λ，非周期的长度大小为μ，

他能在O(λ+μ)的时间复杂度，O(1)的空间复杂度内，得到λ ，μ 。

试用范围：

functional graph：每个点只有一个出度的有向图。

形象的一点说明如果 a_n = f (a_n-1) ，那么你就可以对这个数列用floyed判圈。

（对于这道题就是 a_n = F (a_{n-1 ,}b_n-1) , b_n = G (a_{n-1 ,}b_n-1) , 所以自然适用。）

再比如链表 ……

描述及证明：

我们设od为数列的初始状态，Next()为让a_n-1推出a_n的递推函数，和两个变量 turt ， hare ，相遇点为 x , 进环点为 o。

首先我们令 turt = hare = od ;

然后我们令turt ， hare开始移动 : turt 没回合移动一个点，表示为 turt = Next (turt) ; hare 每回合移动两个点，表示为 hare = Next ( Next (hare)) ;

如果画成图的话，你可以形象的认为，turt每回合只走一步，hare没回和走两步。

然后我们可以得到两个结论：

如果Next () graph 没有环，那么在任何时刻 turt != hare ，并且两者是充要的。
如果Next () graph 有环，那么必然会有 turt == hare 的时候，让我来证明一下：

　　　　　　　　 Floyed判环/龟兔算法

　　hare跑啊跑啊，进到圈里了，但是他永远跑不出去了；turt跑啊~跑啊~ ，终于进圈了，它往逆时针的方向瞟了一眼，发现hare在他后面 y 个节点上，turt 心算了一下再过 y / (2 - 1）的时间hare才追上自己，turt就开心的笑了。

　　我们对 x 时的状态分析一下：

　　turt : i = μ + a·λ + x ;

　　hare : 2·i = μ + b·λ + x ;

　　所以turt 到这一点所走的路程 i = (b - a)·λ -----À

　　让我们继续分析下去，在 x 处turt ， hare相遇了，我们可以认为在这时他们的路程差为 λ ，所以下一次相遇的时间为 λ / (2-1) = λ , 所以我们又可以得到两个结论：

　　　　　　1.如果我们模拟turt ， hare的下一次相遇，那么 turt 所走的路程 1·λ = λ ，所以周期求得。

　　　　　　2.由1可知，两者相遇点仍旧是 x 。

　　最后只剩下 μ 了：

　　　　　　由À可知如果turt再往前走 μ 步，turt必然会回到 o 点，证明：i + μ Ξ μ (mod p) , 又因为从 od 走到 o 点需要 μ 步，所以得证。

　　　　　　那么又要怎么实现呢？我们令 turt 保持在 x 时的状态，让hare = od ；

　　　　　　接下来让 turt ， hare 以每回合都以 turt = Next（turt) , hare = Next (hare) 运动，那么他们又会相遇了，这一次显然是在o点相遇，记录这个走的步数及得到 μ 。

　　伪代码：

void Floyed () {

        pii hare = od , turt = od;

        lam = mu = 0 ;

        int cnt = 0 ;

        while(1) {

                hare = Next (Next (hare) ) ;

                turt = Next ( turt) ;

                if (hare.F == turt.F && hare.S == turt.S)  break ;

        }

        while (1) {

                hare = Next (Next (hare) ) ;

                turt = Next (turt) ;

                lam ++ ;

                if (hare.F == turt.F && hare.S == turt.S)  break ;

        }

        hare = od ;

        while (1) {

                hare = Next (hare) ;

                turt = Next (turt) ;

                if (hare.F == turt.F && hare.S == turt.S)  break ;

                mu ++ ;

        }

        printf ("mu = %d , lam = %d\n" , mu , lam) ;

}