數字計數問題：統計區間內各數字出現次數

問題描述

給定整數區間 [a, b]，列出所有整數，統計 0-9 每個數字出現的總次數。多組輸入，以 0 0 結束。

算法思路

暴力遍歷每個數字轉字符串統計在數據範圍 10^8 內會超時。需採用數位 DP 或數學規律按位計算。

核心邏輯（按位計數法）

對於每一位（個、十、百...），計算該位上 0-9 出現次數：

• 高位 = n / (factor * 10)
• 當前位 = (n / factor) % 10
• 低位 = n % factor
• 根據當前位值分情況累加各數字計數。

參考資源

• 數位 DP 詳細解析
• C++ 實現代碼

複雜度

時間 O(log₁₀ n) 每查詢，可處理 500 組最大 10^8 數據。

掌握數位統計模板，可高效解決此類計數問題。