題目

題目敘述

給你一個區間 $[a, b]$，保證端點都 valid，要你求取區間中 valid 的數字個數。

所謂 valid 的數字，他要符合

  1. 該數字沒有包含9 e.g. 1可以, 191不行
  2. 該數字並非9的倍數 e.g. 1可以, 18不行

思路

我們可以如何排除包含9的數字呢？用九進位來看！

試想，如果把 $[0, 26)$ 這個區間的所有數字都列出來，你會刪掉的數字分別是 $9, 19$。誒，這不就是 $[0, 26)$ 用九進位來看會自動排除掉的數字嗎？利用這個性質，我們可以很簡單的獲得區間內數字個數了！

排除了包含九的數字後，九的倍數怎麼辦？傷為觀察一下就有囉！

AC Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

bool ok(ll x)
{
    if (x % 9 == 0)
        return false;
    while (x > 0) {
        if (x % 10 == 9)
            return false;
        x /= 10;
    }
    return true;
}

ll f(ll x)
{
    // get valid number count
    ll xx = x - x % 10;
    ll cnt = 0;
    for (ll i = 1; xx > 0; xx /= 10, i *= 9) {
        cnt += (xx % 10) * i;
    }

    // remove multiple of 9 count
    cnt = cnt * 8 / 9;

    // enumerate the remaining interval
    for (ll i = x - x % 10; i <= x; i++) {
        if (ok(i))
            cnt++;
    }

    return cnt;
}

ll solve()
{
    ll a, b;
    cin >> a >> b;

    return f(b) - f(a) + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int ncase;
    cin >> ncase;
    for (int i = 1; i <= ncase; i++) {
        cout << "Case #" << i << ": " << solve() << endl;
    }

    return 0;
}