【每日一题】数码 题解

Solution

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1e6  + 5;
const ll mod = 998244355;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll p;
ll solve(ll x){
  ll res = x / p; 
  for(ll st = p * 10, ed = min(x, p * 10 + 9); st <= x; st *= 10, ed = ed * 10 + 9){
    ll realed = min(ed, x); // 右端点不能超过x
    for(ll i = st, mx = 0; i <= realed; i = mx + 1){
      //cout << x << ' ' << p << ' ' << i << ' ' << res << "\n";
      ll sum = x / i; // 
      mx = min(x / sum, realed); 
      res += sum * (mx - i + 1); // 整除个数 * 块的长度 
      i = mx + 1; // 到下一个块
    }
  }
  return res;
}
int main(){
  ll L, R;
  cin >> L >> R;
  for(p = 1; p <= 9; p++){
    cout << solve(R) - solve(L - 1) << "\n";
  }
  return 0;
}