# 求 0~n 當中有幾個數字 $k(0 \le k \le 9)$

### 想法 :
若 $k=0$ ，則要分開討論

#### **1.** $k=0$

我們逐位討論，每一次將數字分為 $cur,$ $high,$ $low$ ，分別是現在這一位數，在他左邊的數，以及在他右邊的數。

以 $1034$ 為例：
$\;\;\;$ 第一次進入迴圈時 $high=103,$ $cur=4,$ $low=0,$ $base=1$。
$\;\;\;$ 因為 $cur \ne 0$ ，因此會有 $10,20,30...1030$ ，共 $103$ 個 $0$。

$\;\;\;$ 第二次進入迴圈時 $high=10\;\;,$ $cur=3,$ $low=4,$ $base=10$。
$\;\;\;$ 同樣因 $cur \ne 0$ ，因此會有 $100,101,102...300...1000$ ，共 $100$ 個 $0$。

$\;\;\;$ 第三次進入迴圈時 $high=1\;\;\;\;,$ $cur=0,$ $low=34,$ $base=100$。
$\;\;\;$ 這次 $cur=0$ ，因此會有 $1000,1001,1002...1034$ ，共 $35$ 個 $0$

最後不要忘記還有 $0$ 本身也是一個。

#### **2.** $k>0$

同樣逐位討論，每一次將數字分為 $cur,$ $high,$ $low$ ，分別是現在這一位數，在他左邊的數，以及在他右邊的數。

以 $n=1034,\;k=2$ 為例：
$\;\;\;$ 第一次進入迴圈時 $high=103,$ $cur=4,$ $low=0,$ $base=1$。
$\;\;\;$ 因為 $cur > k$ ，因此會有 $2,12,22,32...1032$ ，共 $104$ 個 $2$。

$\;\;\;$ 第二次進入迴圈時 $high=10\;\;,$ $cur=3,$ $low=4,$ $base=10$。
$\;\;\;$ 同樣因 $cur > k$ ，因此會有 $20,21,22,23...320...1020$ ，共 $110$ 個 $2$。

$\;\;\;$ 第三次進入迴圈時 $high=1\;\;\;\;,$ $cur=0,$ $low=34,$ $base=100$。
$\;\;\;$ 這次 $cur < k$ ，因此會有 $200,201,202...299$ ，共 $100$ 個 $2$

### 實作 :

// just for 0
ll countDigit(ll n){
    if(n<1) return 1;
    ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
    while(high>0){
        high=n/(10*base);
        tp=n%(10*base);
        cur=tp/base;
        low=tp%base;
        if(cur==0){
            ret+=(high-1)*base+low+1;
        }else{
            ret+=high*base;
        }
        base*=10;
    }
    return ret+1;
}

// only for 1~9
ll countDigit(ll n,ll k){
    if(k==0) return countDigit(n);
    ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
    while(high>0){
        high=n/(10*base);
        tp=n%(10*base);
        cur=tp/base;
        low=tp%base;
        if(cur==k){
            ret+=high*base+low+1;
        }else if(cur<k){
            ret+=high*base;
        }else{
            ret+=(high+1)*base;
        }
        base*=10;
    }
    return ret;
}

###### tags: `程式設計`