【每日一题 4.6】数码

题意:

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

题解

最先想到的是枚举[L,R]区间内的每一个数,然后求和。
考虑如何优化。
我们发现只用写出最高位出现的次数所以
下来就是来计算每个 对应的区间
比如 那么最后决定答案的是什么?不就是 在范围的倍数的个数如
然后呢就是如果每一个都要计算的话,那么时间复杂度为 ,这样接着超时(弥天大雾)
举个例子 ,在 的符合的倍数的个数都为 个,所以就可以相当于111*9,然后就可以跳过一部分枚举区间
时间复杂度:

Code

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define Each(i) for (rint i = head[u]; i; i = edge[i].nxt)
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

ll l, r;
ll a[20], b[20];
ll calc(ll x) {
  ll ans = 0;
  while (x > 0) {
    ans += x % 10;
    x /= 10;
  }
  return ans;
}
void solve(ll *a, ll r) {
  for (ll i = 1; i <= sqrt(r); i++) {
    ll b = r / i;
    for (ll j = 1; j <= r; j *= 10) {
      for (ll k = 1; k <= 9; k++) {
        int x = max(j * k, i + 1);
        int y = min(j * (k + 1) - 1, b);
        if (x <= y) {
          a[k] += y - x + 1;
        }
      }
    }
    a[calc(i)] += b - i + 1;
  }
}
int main() {
  while (~scanf("%lld%lld", &l, &r)) {
    solve(a, r);
    solve(b, l - 1);
    for (rint i = 1; i <= 9; i++) {
      printf("%lld\n", a[i] - b[i]);
    }
  }
  return 0;
}