我们可以观察一下1/10这组数据，按照二进制转换法(乘二法)，我们可以得到：
1/10  2/10 4/10 8/10 16/10 32/10 ...
然后都分子都尽可能减去10，得到：
1/10  2/10 4/10 8/10 6/10 2/10 ...
这时候，发现出现了重复，那么这个重复就是我们要求的最小循环。
抽象出模型如下：对p/q
首先p'=p/gcd(p,q)
q'=q/gcd(p,q);

然后我们就是求p'*2^i == p'*2^j (mod q')   (“==”表示同余,i<j)
经过变换得到：
p'*2^i*(2^(j-i)-1) ==0 (mod q')
也就是 q' | p'*2^i*(2^(j-i)-1)
由于gcd(p',q')=1,
得到： q' | 2^i*(2^(j-i)-1)
因为2^(j-i)-1为奇数，所以q'有多少个2的幂，i就是多少，而且i就是循环开始位置的前一位。
那么令q''为q'除去2的幂之后的数
此时 q'' | 2^(j-i)-1
也就是求出x,使得 2^x ==1 (mod q'')
由于q''和2互质，所以必定有解，而且这个是属于高次同余方程，有经典的方法可以做，大家可以自己去查阅资料解决。

• Re:说说我的做法 (2) 392377379 2014-04-02 19:47:53