今天又做了一个组合数学的题目。

题目描述：

题目为POJ1150

题目描述是：

题目描述：

题目描述如下：

不过我做的一个题目还是挺有收货的呢。

题目描述：

说到dp，这是我的一个弱项，我觉得这个东西很难以理解，虽然dp题目几乎每场比赛都有哦。

今天做了一个多校赛的dp题。名字是Capturing a country。
……

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

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

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

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

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