每日一题 - 统计数字问题

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

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



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

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

因为最后一位提到前面后与原数为二倍关系，但是总位数不变
所以可以设最后一位最小为2，前面一位数为后面位数的二倍，进位保留在更前面的一位上；
则当计算到第一位为1，且第二位小于5时所得到的数既为所求，过程如下：
.................2
................42
...............842
..............6842
.............36842
............736842
...........4736842
..........94736842
.........894736842
........7894736842
.......57894736842
......157894736842
.....3157894736842
....63157894736842
...263157894736842
..5263157894736842
.05263157894736842
105263157894736842
以上数字，最后一位为2，正好是第一位1的2倍，且第二位0小于5，所以满足设定得解。
所以所有以105263157894736842为循环节的数都满足这个要求。

另外，所有满足“最后一位为第一位的2倍，且第二位小于5”这个设定的数都满足题目要求。
如：
315789473684210526
210526315789473684
421052631578947368等等...

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

An n-parasitic number for n=2~9, is a such that, when by n, the of the result is the same as for the original , except with the rightmost 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的数，通过尝试即可得到

按照上的说法应该更简单了， 因为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
6	10169491525423728813559932203389830508474576271186440677966
7	1014492753623188405797
8	1012658227848
9	10112359550561797752808988764044943820224719