【每日一题】数码

Description

给定两个整数 $l$ 和 $r$ ，对于所有满足 $1 ≤ l ≤ x ≤ r ≤ 10^9$ 的 $x$ ，把 $x$ 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求 $1～9$ 每个数码出现的次数。

Solution

一个很显然的思路是，枚举以 $x$ 开头的数，计算它的倍数在 $[l, r]$ 中出现的次数。
我们设 $f(n, i)$ 为 $i$ 的倍数在 $[1, n]$ 中出现的次数，那么有 $f(n, i) = \lfloor{\frac{n}{i}}\rfloor$
故而 $i$ 的倍数在 $[l, r]$ 中出现的次数就是 $f(r, i) - f(l - 1, i)$

那么，题目中的问题便是对每个 $x \in [1, 9]$ 求 $\sum_{i=x\cdot{10^{0}}}^{(x+1)\cdot{10^{0}-1}}(f(r,i)-f(l-1,i)) + \sum_{i=x\cdot{10}}^{(x+1)\cdot{10}-1}(f(r,i)-f(l-1,i)) + \sum_{i=x\cdot{10^{2}}}^{(x+1)\cdot{10^{2}}-1}(f(r,i)-f(l-1,i))+...$

如果直接对枚举的区间进行计算，复杂度是 $\rm{O}(n)$ 的，这显然不能接受。
所以我们需要用到一个“整除分块”的技巧，以达到在 $\rm{O}(\sqrt{n})$ 的复杂度下计算 $\sum_{i=x}^{y}\lfloor\frac{n}{i}\rfloor$ 的目的。

Code

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

using ll = long long;

ll get(int x, int v) {
  ll res = 0;
  for (ll pw = 1; pw <= x / v; pw *= 10) {
    int cur = v * pw, bound = min<ll>(x, cur + pw - 1);
    // 枚举区间[cur, bound]
    for (int i = cur, j; i <= bound; i = j + 1) {
      j = min(x / (x / i), bound);
      res += 1ll * (j - i + 1) * (x / i);
    }
  }
  return res;
}

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  int l, r;
  cin >> l >> r;
  for (int i = 1; i <= 9; i++) {
    cout << get(r, i) - get(l - 1, i) << "\n";
  }
}