求[0-n]中含至少一个9的整数个数：公式及代码问题排查

通用计算方法 #

要计算[0,n]中至少包含一个9的整数个数，最高效的思路是反向推导：

1. 先算出[0,n]中完全不包含数字9的整数个数，记为count_no_9
2. 最终结果 = (n + 1) - count_no_9（因为0到n共包含n+1个整数）

计算count_no_9的核心逻辑 #

将n的十进制各位从高位到低位依次处理：

• 初始化count = 0
• 对每一位数字d（从左到右）：
  • 若d < 9：累加d * 9^k（k为当前位右侧的位数，对应后面每一位都有0-8共9种选择）
  • 若d == 9：累加当前位的贡献后直接终止循环（后续所有以当前前缀开头的数都包含9，无有效贡献）
• 若n本身不含9，最后需额外加1（把n本身计入不含9的数中）

你的代码问题分析 #

1. 公式逻辑错误 #

你用n - a作为结果，但正确公式应该是(n + 1) - a——[0,n]包含n+1个整数，而非n个。比如n=9时，正确结果是1，你的代码返回9-9=0，就是因为这个错误；n=3950时，正确总数是3951，3951-2916=1035，而你的代码用3950-2916=1034，正好差1。

2. 精度丢失严重 #

你大量依赖double类型做转换和计算：

• Math.Log10((double)n)：当n是极大的BigInteger时，double无法精确表示，导致位数计算错误
• Math.Pow(10, (double)i)、Math.Pow(9, (double)i)：double精度有限，当i≥16时，无法准确表示整数幂，导致计算结果偏差
• BigInteger转double：当n超过2^53时，double无法存储精确整数值，后续除法、取模计算全部出错

3. 循环方向逻辑漏洞 #

你从低位到高位处理数字，但计算不含9的数的逻辑更适合从高位到低位推进，低位到高位的处理方式容易忽略前缀限制，引发逻辑错误。

修正后的C#代码示例 #

using System;
using System.Numerics;
using System.Collections.Generic;

public static class Kata {
    public static BigInteger Nines(BigInteger n) 
    { 
        BigInteger countNo9 = 0;
        BigInteger temp = n;
        BigInteger power9 = 1; // 初始为9^0=1
        
        // 将数字拆分为高位到低位的列表
        var digits = new List<int>();
        if (temp == 0) {
            digits.Add(0);
        }
        while (temp > 0) {
            digits.Add((int)(temp % 10));
            temp /= 10;
        }
        digits.Reverse();
        
        bool hasNine = false;
        foreach (int d in digits) {
            if (hasNine) break;
            
            if (d < 9) {
                countNo9 += d * power9;
            } else {
                countNo9 += 9 * power9;
                hasNine = true;
            }
            power9 *= 9;
        }
        
        // 若原数不含9，需将其本身计入不含9的数中
        if (!hasNine) {
            countNo9 += 1;
        }
        
        return (n + 1) - countNo9;
    }
}

测试验证：n=3950返回1035，n=9返回1，n=0返回0，均符合预期。

内容的提问来源于stack exchange，提问作者konrad