【每日一题】数码

Description

给定两个整数 和 ，对于所有满足 的 ，把 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求每个数码出现的次数。

Solution

一个很显然的思路是，枚举以开头的数，计算它的倍数在中出现的次数。
我们设为的倍数在中出现的次数，那么有
故而的倍数在中出现的次数就是

那么，题目中的问题便是对每个求

如果直接对枚举的区间进行计算，复杂度是的，这显然不能接受。
所以我们需要用到一个“整除分块”的技巧，以达到在的复杂度下计算的目的。

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";
  }
}