声明：这篇博文主要整理自百度之星大赛讨论区goodbyeworld的留言，有些地方我做了些修改，也加入了不少对细节的证明。
正文：
“2013.3.31百度之星，线性同余发生器 求序列周期（1）”中最后的问题主要集中在当q是奇数的时候，生成的序列具有什么样的周期，以及从哪里开始进入周期的循环。
针对 mi+1= (q2mi
+ 1) mod 2n 这个发生器已经找到它的周期了。
先给出模运算的几个性质：
证明：
如果x<=2^n,y=x,显然成立；
接下来只考虑x>2^n,
把x写成这个形式：x=p*2^k，求余的过程可以表示成
p*2^k-c*2^n=b*2^a,其中p，b不含有因子2，c可能含有因子2，k<=n，我们想证明a=k。
整理一下，2^k*[p-c*2^(n-k)]=b*2^a。
先证明p-c*2^(n-k)不含因子2，假设它含有因子2，它可以写成p-c*2^(n-k)=2^d，
p=2^d+c*2^(n-k)，2^d+c*2^(n-k)肯定可以提取因子2，这与p不含有因子2矛盾，所以p-c*2^(n-k)不含因子2。
所以a=k肯定成立，不然的话与2^k*[p-c*2^(n-k)]=b*2^a矛盾（相等含有因子2的数目肯定相等）。over！
3.奇数的平方模4余1
我们设c=0，所以序列从X(0)=0启动，X(k+1)=(q^2*X(k)+1)mod(2^n)
应用性质（1）（4）可以得到X(k)=sum(q^(2i),i=0..k-1)%(2^n)，即X(k)=[1+q^2+q^4+...+q^(2(k-1))]%(2^n)
1，q^2，q^4，...，q^(2(k-1))的每一项都是奇数，显然
1
q^2+1
q^4+q^2+1
q^6+q^4+q^2+1
.... ....
是奇偶交替的。
又因为“奇数mod偶数=奇数，偶数mod偶数=偶数”，所以
x1=1%2^n
x2=(q^2+1)%2^n
x3=(q^4+q^2+1)%2^n
x4=(q^6+q^4+q^2+1)%2^n
... ....
也是奇偶交替的。即X(0),X(1),X(2),X(3),......也是奇偶交替的。
S[1]={X(1),X(3),X(5)....}是奇数数列
X(2k)
=[1+q^2+q^4+...+q^(2(k-1))+...+q^(2(2k-1))]%(2^n)
=[1+q^2+q^4+...+q^(2(k-1))(1+q^(2k))]%(2^n) (提取公因子)
=[X(k)*(1+q^(2k)) ]mod(2^n)（反复应用性质3）
因为'奇数的平方模4余1'，q^(2k)是奇数，q^(2k)%4=1，所以1+q^(2k)可以被2整除，但是不能被4整除。（同样可以用模运算的定义说明）
S[2]={X(2),X(6),X(10),X(14)...｝= S[1] *｛1+q^2,1+q^6,1+q^10,....｝mod 2^n,每一项可以被2整除，但不被4整除 （引理2.)
S[4]={X(4),X(12),X(20),X(28),...}=S[2]*{1+q^4,1+q^12,1+q^20,....} mod 2^n,每一项可以被4整除，但不被8整除 （引理2.)
归纳S[8],S[16],...S[2^n]都是类似的性质，即S[2^t]中的元素含有因子2的数目为t。这个规律很好，X(1),....X((2^n)-1)都含有因子2，不为0，直到S[2^n]={X(2^n)}=0。
除了X(0)=0,下一个X(k)=0出现是X(2^n) =0. 所以2^n是一个周期。
假设存在比2^n更小的周期，那么存在0<=a<b 且b-a<2^n，并 有X(a)=X(b)，
0=X(b)-X(a)
=sum(q^(2i),i=a,a+1,...,b-1)mod 2^n
= q^(2a)*sum(q^(2i),i=0..b-a-1) mod(2^n)
=q^(2a)*X(b-a)mod 2^n.（反复应用性质3）
q^(2a)是奇数，X(b-a)=0（若不等于0，q^(2a)*X(b-a)mod 2^n不可能为0，因为q^(2a)*X(b-a)这个里面含有因子2的数目不会大于等于n的） , b-a<2^n，这与 X(2^n)=0 才是下一个0项矛盾。
所以最小周期就是2^n
X(k)的可能的取值只有0..2^n-1，周期是2^n，所以X[0..(2^n-1)]取遍[0..(2^n-1)]，达到满周期。
现在解决这个题目一个自然的想法就是只要找到 c，x距离0的位置a，b，那么a，b之间的距离就是答案了。也就是任意给定一个数y，确定这个数需要迭代几步会到达0.
我们可以先确定y最大被2的几次幂整除 ，假设是t。
借助上面的S[1],S[2],S[4],S[8]...数列，知道y在S[2^t]里。y迭代2^t步后得到z，z就至少在S［2^(t+1)]，或者更后的S[2^(t+??)]里。
对于上面这句话，这里给出一个证明。假设y开始的位置为i（我们并不知道i的具体数值），i=2^t*p，p中不含有因子2为奇数。
i+2^t=2^p+2^t
=2^t(p+1)=2^(t+？？)q
最后的推导表示从p+1中尽可能多的提取因子2（至少含有一个）。
然后再判断Z含有的因子2的数目，如此循环直到迭代到0出现。
伪代码写出来如下
cnt = 0
while h ==0
L :=Lowbit (h) //用lowbit 运算得出最大被2的多少次幂整除。
h := (h * ((q^2)^(L))+ (1+q^2+q^4 + ... +(q^2)^(L-1)))mod (2^n) //h迭代L步，需要倍增快速计算
cnt:=cnt + L //计数迭代的总布数
cnt就是需要找的迭代步数。
--------------------------------------------------------------------------------------------------------------------割----------------------------------------------------------------------------------------------------------------
讨论：
1.我们挖掘S[1],S[2],S[4],S[8]...数列的规律一方面发现了满周期，最主要的是为了后面的快速迭代（没感觉出来这个能快多少？存储1+q^2+q^4 + ...这些值 迭代更快），其实发现满周期后一步步迭代不知道能不能AC。
2.拓展一下，对于其他形式的发生式怎么去发现周期规律呢?