[51NOD] 1009 数字1的数量 [数学][详解]

给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。 例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。 Input 输入N(1 <= N <= 10^9) Output 输出包含1的个数 Input示例 12 Output示例 5

题解

提供一组数据 输入127948输出99344 不是很好想

记n的长度为L$L$，设f(x)$f(x)$ 为小于x的包含1的个数 1. 长度小于L$L$的 即求 f(10L)$f(10^L)$ 利用数学归纳法可以得到 f(10k+1)=f(10k)⋅10+10k $$f(10^{k+1})=f(10^k)/cdot 10+10^k$$ 那么不难求得该情况下的答案 2. 长度等于L$L$的 该情况就有点复杂了 设g(x)$g(x)$ 为第x位到个位的包含1的个数，记第x位的数字为Rx$R_x$ ，记第x位后面的数Cx=Rx−1⋅10x−2+Rx−2⋅10x−3+…+R1$C_x=R_{x-1}/cdot 10^{x-2}+R_{x-2}/cdot 10^{x-3}+…+R_1$ 那么当x<L$x<L$ 时 g(x)=⎧⎩⎨⎪⎪g(x−1)+Rx⋅f(10x−1)+10x−1,g(x−1)+Rx⋅f(10x−1)+Cx,g(x−1),Rx>1Rx=1Rx=0 $$g(x)=/begin{cases} g(x-1)+R_x /cdot f(10^{x-1}) +10^{x-1}, & R_x>1 // g(x-1)+R_x /cdot f(10^{x-1}) +C_x, & R_x=1// g(x-1), & R_x=0 /end{cases}$$ 当x=L$x=L$ 时 g(x)=⎧⎩⎨⎪⎪g(x−1)+(Rx−1)⋅f(10x−1)+10x−1,g(x−1)+(Rx−1)⋅f(10x−1)+Cx,g(x−1),Rx>1Rx=1Rx=0 $$g(x)=/begin{cases} g(x-1)+(R_x -1)/cdot f(10^{x-1}) +10^{x-1}, & R_x>1 // g(x-1)+(R_x -1)/cdot f(10^{x-1}) +C_x, & R_x=1// g(x-1), & R_x=0 /end{cases}$$

我的代码有点乱