根据页码所用数字量求书籍总页数：C#低效算法需优化（支持1e9级n）

嘿，我懂你的困扰！当n达到10^9这种量级时，你原来的逐页遍历累加数字位数的方法肯定会超时——毕竟要循环几百万甚至上千万次，完全没法在1秒内跑完。咱们换个数学分段计算的思路，直接把时间复杂度降到O(log n)，轻松搞定大数值的情况！

原代码的问题分析 #

你原来的代码是这样的：

using System;
struct MainStruct {
    private static void Main () {
        int n = int.Parse (Console.ReadLine ());
        int page = 1, count = 0;
        while (true) {
            count = count + page.ToString ().Length;
            if (count == n) {
                break;
            }
            page = page + 1;
        }
        Console.WriteLine (page);
    }
}

它的问题在于线性遍历：每一页都要转成字符串计算长度再累加，时间复杂度是O(page)，当n=1e9时，page会接近1.1e8，循环次数太多必然超时。而且用int存储n和count还有溢出风险，因为1e9已经接近int的最大值（2^31-1=2147483647）。

高效算法思路 #

我们可以按页码的位数分段计算，每个位数区间的数字使用量是固定的：

• 1位页码（1-9）：共9页，使用9*1=9个数字
• 2位页码（10-99）：共90页，使用90*2=180个数字
• 3位页码（100-999）：共900页，使用900*3=2700个数字
• ...
• k位页码：共9*10^(k-1)页，使用9*10^(k-1)*k个数字

具体步骤：

1. 用long类型存储数值，避免溢出
2. 从1位开始，依次减去当前区间的数字总数，直到剩余的n小于等于当前区间的数字总数
3. 计算剩余数字对应的页码数，加上前面的总页数得到最终结果

优化后的C#代码 #

using System;

class Program
{
    static void Main()
    {
        // 用long存储n，避免1e9级别的数值溢出
        long n = long.Parse(Console.ReadLine());
        long totalPages = 0;
        int digitLength = 1;
        long currentRangePages = 9; // 当前位数区间的总页数，初始为1位的9页

        // 逐步减去各个位数区间的数字使用量，定位到目标区间
        while (n > digitLength * currentRangePages)
        {
            n -= digitLength * currentRangePages;
            totalPages += currentRangePages;
            digitLength++;
            currentRangePages *= 10;
        }

        // 计算当前区间内的页码数
        totalPages += n / digitLength;
        // 如果有余数，说明还多一页（比如n=10，剩余1个数字对应10的第一位）
        if (n % digitLength != 0)
        {
            totalPages++;
        }

        Console.WriteLine(totalPages);
    }
}

测试例子 #

• 输入9 → 输出9（1-9刚好使用9个数字）
• 输入10 → 输出10（9个数字用在1-9，剩余1个数字对应10的第一位）
• 输入189 → 输出99（9+180=189，刚好覆盖1-99）
• 输入190 → 输出100（189个数字到99，剩余1个数字对应100的第一位）

这个算法不管n多大，循环次数最多就是页码的位数（比如1e9是9位，循环最多8次），完全能在1秒内处理1e9的数值。

内容的提问来源于stack exchange，提问作者D. Doduhyyy