【每日一题】数码

首先，对于求区间 [l, r] 的问题，可以转换成求 [1, r] 的问题。答案为 [1, r] 的结果减去 [1, l - 1] 的结果。
然后，需要分别统计最高位数字不同的约数的出现的次数，我们可以转变思路，枚举约数，统计每个约数在区间中出现的次数。
假设这道题没有区分最高位，只是求约数个数，那就是一道经典的数论分块题目，求 [l, n] 中每个数约数的个数和，枚举约数，问题转换成求 ，直接计算的复杂度是
可以通过打表观察到， 到 的间隔会越来越大。于是我们就可以通过计算每个 的区间 [l, r] 的长度，快速计算每段区间的和，因为 的取值大约只有 个，复杂度为 ，具体复杂度证明请百度。
但是现在需要对每种数码进行区分，只需要在每次分块过程中将最高位不同的数分开统计就行了。
求一个区间中最高位为 x 出现的次数，这个问题应该是有很多做法。因为最高位数相同且位数相同的数字是连续的，所以对于每一种数码，可以枚举位数来计算出区间中这个数码出现的次数。

#include <bits/stdc++.h>
using namespace std;
static auto faster_iostream = []() { ios::sync_with_stdio(0); cin.tie(0); return 0; }();
typedef long long ll;

ll ans[10];

void solve(int n, int op) {
  for (ll l = 1, r; l <= n; l = r) { // [l, r)
    r = n / (n / l) + 1;
    for (int i = 1; i <= 9; i++) {
      int len = 0;
      for (ll L = i, R = i + 1; L < r; L *= 10, R *= 10)
        len += max(0ll, min(r, R) - max(l, L));
      ans[i] += op * len * (n / l);
    }
  }
}

int main() {
  int a, b;
  cin >> a >> b;
  solve(b, 1);
  solve(a-1, -1);
  for (int i = 1; i <= 9; i++) {
    cout << ans[i] << '\n';
  }
}