PAT 1049 Counting Ones：數位 DP 數學公式 O(log N) 解法

題目

給定 N (≤ 2³⁰)，求 1 到 N 所有整數十進制表示中數字 1 出現的總次數。

示例：N=12 → 1,10,11,12 含五個 1 → 輸出 5。

數學推導：逐位計數

對每一位（個、十、百…），設當前位權 factor = 10^k，
higher = N / (factor*10)，cur = (N / factor) % 10，lower = N % factor。
該位上 1 出現次數：

• cur == 0：higher * factor
• cur == 1：higher * factor + lower + 1
• cur > 1：(higher + 1) * factor

C++ AC 代碼

#include 
using namespace std;

long long countOnes(long long n) {
    long long cnt = 0, factor = 1;
    while (n / factor) {
        long long higher = n / (factor * 10);
        long long cur = (n / factor) % 10;
        long long lower = n % factor;
        if (cur == 0) cnt += higher * factor;
        else if (cur == 1) cnt += higher * factor + lower + 1;
        else cnt += (higher + 1) * factor;
        factor *= 10;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long N; cin >> N;
    cout << countOnes(N) << "\n";
    return 0;
}

複雜度

• 時間：O(log₁₀ N)，最多 10 位循環。
• 空間：O(1)。

來源

《編程之美》「計算 0 到 N 包含數字 1 的個數」章節。