题目的大意为给你一个分数p/q，如121/1472这样的分数。

题目要你求出小数点后面循环开始的位置i以及循环节的长度。

刚开始看题的时候就懵了，虽然高中以前做过这种进制转化，以及变小数的题目，但是老衲真心不记得了。今天这个题目还是真的挺有用的。

言归正传，根据题目的意思，很容易让人想到的是用朴素的方法每次乘以2然后取余（我没有试过，不知道这样暴力能不能过），但是这种方法显然不是最优的办法呢。

下面就用比较正式一点的数论知识解决这个问题吧。

首先对于p和q我们显然可以先求出他们的最大公约数d，并分别用d去除p和q。

这样得到了新的p和q。（还可以p=p%q，这样保证了p<q）

第二步就是进行一定的化简了哦。

首先对于任何整数，我们都可以表示为q=r*(2^m)，显然这是没有问题的。

对于分子可以分解为 p=r*t+x（这里的r是分母分解出来的那个r）

首先不看2^m，先看(r*t+x)/r=t+x/r，这里t为一个整数，所以对于这个数，它在小数点的前面呢，不用管。同时这里x和r也是互素的（想想为什么？）于是循环节的长度就是x/r在二进制中的循环的长度。不妨设(x*2^a)=(x*2^b)(mod r)，这样就等价于2^|a-b|=1(mod r)，于是看到这个东西肯定就瞬间明白了一点什么了呢。对没错，循环的长度就是euler(r)。但是我实践了一下，答案不对，为什么会不对呢？惊奇地，我发现这里长度答案是标准的一个倍数。所以这里的答案可能是euler(r)的某一个约数呢。所以我们要枚举它的约数这样才能确定最短的循环长度（其实题目里面有提示哦）。

对于循环开始的位置，那就更加容易了。上面说到(r*t+x)/r为一个整数，于是就看下面的2^m这里相当于小数点左移了m位，加上原来应该有的一位是m+1位。这样一来这个问题就完美解决了。（参考自某个不知名的神牛）

极力推荐对数论有兴趣的同学去做做这个题目。

下面附上我的代码：

(*^__^*) 嘻嘻……