摘自算法设计与实验题解 算法实现题1-1

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。



==================== 上题分析 =====================
Parasitic Number - 把一个多位数的最后一位提到第一位后这个数是原数的两倍求原数

一、比较笨的一个推理方法


二、数学推理
从wiki上可知这样的数称为Parasitic Number,定义为：

An n-parasitic number for n=2~9, is a natural number such that, when multiplied by n, the decimal representation of the result is the same as for the original number, except with the rightmost digit moved to the front. In other words, the decimal representation undergoes a right circular shift by one place.
一个n阶parasitic number是指这样的自然数，把它乘以n以后得到的数恰好就是把它的个位数拿到最前面得到的数。

本题实际上就是求2阶的parasitic number。

设此数为10x+y，y为个位数，x为此数其余部分，再设p为此数的位数，则p=(lgx)+1，根据题意可知：
(10^p)*y + x = n *(10*x + y)

x = ((10^p - n)*y) / (10n-1)
原数为10x+y, 得: 10x + y = ((10^q -1) * y) / (10n-1)

注意这里有三个未知数，q是此数的位数+1，y是个位数，n是题目中的n（本题为2）。wiki和转载的一些文章好像是把y也写作n了

对于给定的n，我们必须寻找这样的数字，9, 99, 999, ...，从中找出其能够被 (10n-1)/y整除的。比如5， 10-1=49，因为49只有7，1，49这三个因子，所以必须必须找到能够整除7或者49的数，通过尝试即可得到

按照wiki上的说法应该更简单了， 因为y/(10n-1)是循环小数，可以表示为类似z*0.000100010001...的形式，其中z是循环节，而另一部分中0的个数就是循环节的长度。另外我们注意到1/9, 1/99, 1/999，...恰好也是类似的形式，所以y/(10n-1)可以表示为z/(10^p - )，其中p为循环节的长度。这样求解就变得非常简单

下面是最小的n阶parasitic number

n	Smallest n-parasitic number
2	105263157894736842
3	1034482758620689655172413793
4	102564
5	142857
6	10169491525423728813559932203389830508474576271186440677966
7	1014492753623188405797
8	1012658227848
9	10112359550561797752808988764044943820224719