题解 | #数圈圈#

考察知识点：前缀和

使用 $x[i]x[i]$ 记录数字 $ii$ 的圈数，$s[i]s[i]$ 记录 ${\sum }_{j=1}^{i}x[j]\backslash sum\backslash limits\_\{j=1\}^\{i\}\; x[j]$，即前缀和。 则数字 $aa$ 到 $bb$ 的总圈数为 $s[b]-s[a-1]s[b]\; -\; s[a-1]$。

时间复杂度：$O(n\log n)O(n\; \backslash log\; n)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 1000000

ll quan[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
ll x[N+1], s[N+1];

void init()
{
    for (ll i = 1; i <= N; i++)
    {
        ll tmp = i;
        while (tmp)
        {
            x[i] += quan[tmp % 10];
            tmp /= 10;
        }
    }
    for (ll i = 1; i <= N; i++)
        s[i] = s[i - 1] + x[i];
}

void solve()
{
    ll a, b;
    cin >> a >> b;
    ll ans = s[b] - s[a - 1];
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    init();
    cin >> t;
    while (t--)
        solve();
    return 0;
}