《編程之美》：1 到 N 中數字 1 出現的次數及 f(N)=N 最大解

問題 1：計算 1~N 中數字 1 出現總次數 f(N)

按位分治：對每一位（個、十、百…），設 factor=10^k，將 N 分為高位 high、當前位 cur、低位 low。

• cur == 0：該位出現 1 的次數 = high * factor
• cur == 1：次數 = high * factor + low + 1
• cur > 1：次數 = (high + 1) * factor

累加各位結果即得 f(N)。時間 O(log N)。

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

問題 2：求最大 N 使 f(N) = N

觀察規律：

9         : 1
99        : 20
999       : 300
9999      : 4000
...
9,999,999,999 (10位) : 10,000,000,000
99,999,999,999 (11位): 110,000,000,000  // f(N) > N

故解不超過 11 位數。從上界向下暴力搜索首個 f(N)==N 即可（實際答案為 1,111,111,110）。

int main() {
    long long N = 99999999999LL;
    for (long long i = N; i > 0; --i)
        if (countOnes(i) == i) { cout << i << endl; break; }
}