题目描述

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

题解

首先问题可以转化为solve(r)-solve(l-1)的形式
那么考虑如何求1~x中满足题意的数量
既然要求高位，那么我们可以枚举这个最高位，可以看做[1,2),[10,20),[100,200)这样的形式来算1的数量
即，我们要求每个区间里的每个数的倍每个倍数<x的数量，那么对于一个数i，它的倍数<x的数量为 ceil(x/i);
所以问题就转化为对每个区间的sigma(ceil(x/i))。
考虑怎么求这个sigma。直接for循环枚举是肯定不行的，那我们发现，x/i的数有很多都是连续重复出现的并且不同的数只有根号n个，那么我们是否可以O(1)的求出这个区间然后用区间长度*x/i从而得到答案呢？
答案是肯定的，并且对于值为x/i的右区间为x/(x/i)

证明：

[图片]

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 4e6 + 6;
const LL inf = 0x3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

LL l,r;

LL solve(LL x,LL k){
   LL ans=0;
   for(LL v=1;v*k<=x;v*=10){
       LL up=min(x,v*k+v-1);
       for(LL i=v*k;i<=up;){
           LL j=min(up,x/(x/i));
           ans+=(j-i+1)*(x/i);
           i=j+1;
       }
   }
   return ans;
}

int main(){
     scanf("%lld%lld",&l,&r);
     for(int i=1;i<=9;i++){
        printf("%lld\n",solve(r,i)-solve(l-1,i));
     }
}