题目描述

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

预备知识：整数分块

具体证明请看这。
https://www.cnblogs.com/0xfffe/p/9648943.html
下面我们稍微理解一下这个知识。先从求如下式子说起。

首先肯定想暴力枚举（肯定会t） 这里举个例子不妨让x = 15，
我们打表以后的结果：15，7，5，3，3，2，2，1，1，1，1，1，1，1，1.
由于这些数字肯定是递减的并且我们发现有些连续的区间的值是相同的！因此我们不需要枚举所有的数，如果我们能够每次都能够精准的找到连续相等区间的左右端点就好了！
这两个端点其实十分好找。我们假设左端点是i，那么我们需要找的是最远的右端点j使得，i到j区间内的任何一个数p，x/p都相同。右端点j显然是就j = x/(x/i)为什么呢？
其实可以反证法：首先易得j满足x/j = x/i 又由于不严格单调递减，所以i-j区间的数都相等。另一方面，如果p > j 那么x/(j+1) < x/j (因位x是j的倍数)就比如8/3 < 8/2
可以证明这样跳着找的时间复杂度是 具体证明看上面链接。
下面是代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define ll long long
#define LLMax LLONG_MAX
#define LLMin LLONG_MIN
#define PII pair<int,int>
#define Max INT_MAX
#define Min INT_MIN
#define FOR1(i,a,b) for(int i=(a);i<(b);i++)
#define FOR2(i,a,b) for(int i=(a);i<=(b);i++)
#define DWN(j,b,a) for(int j=(b);j>=(a);j--)
#define SET0(a) memset(a,0,sizeof(a))
#define SET1(a) memset(a,-1,sizeof(a))
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int INF=0x3f3f3f3f;
const int NINF=-INF-1;
const double PI=acos(-1);
const int mod=1e9+7;
const int maxn=3e6+5;
using namespace std;

ll solve(int rg, int dg)
{
    ll res = 0;
    for (int i = 1; i <= rg / dg; i *= 10)
    {
        int st = dg * i, ed = min(rg, st + i - 1);
        for (int j = st, k; j <= ed; j = k + 1)
        {
            k = min(rg / (rg / j), ed); 
            res += (k - j + 1) * (rg / j);
        }
    }
    return res;
}

int main()
{
    int l, r;
    cin >> l >> r;
    for (int i = 1; i <= 9; i ++)
        cout << solve(r, i) - solve(l - 1, i) << endl;
}