NC13221 数码（除法分块）

题目描述

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

分析

由于约数和倍数一一对应，我们考虑枚举 $t$ ，然后 $t$ 的倍数就有 $\left\lfloor\frac{x}{t}\right\rfloor$ 个，那么 $t$ 的数码出现次数就加上倍数个数。所以我们考虑某个数的倍数。
由于每个数码独立，我们将每个数码单独考虑，假设考虑数码 $1$ 。
那我们就枚举 $1$ 在个位，十位，百位等等的情况。
假设 $1$ 在第 $k$ 位。
那么范围就是 $[10^k,2*10^k-1]$ ，现在我们要看这个范围内每个数的倍数之和，也就是 $\sum\limits_{i=l}^{r}\left\lfloor\frac{x}{i}\right\rfloor$ 。
然后这个是一个除法分块的问题。关于除法分块，我这里简要说一说。
首先随着 $i$ 增大， $\left\lfloor\frac{x}{i}\right\rfloor$ 是单调不增的，而且相同的 $\left\lfloor\frac{x}{i}\right\rfloor$ 构成一段连续区间。
那么我们假设第一个 $\left\lfloor\frac{x}{i}\right\rfloor$ 出现的位置是 $l$ ，那么最后一个 $\left\lfloor\frac{x}{i}\right\rfloor$ 出现的位置是 $\left\lfloor\frac{x}{\left\lfloor\frac{x}{l}\right\rfloor}\right\rfloor$ ，我们将它记为 $r$ 。这一点不难看出。那么 $\left\lfloor\frac{x}{i}\right\rfloor$ 出现的次数就为 $r-l+1$ 次。将它计入答案，然后将 $l$ 跳到 $r+1$ 即可，如此循环下去。
代码长这样：

for(l = ll; l <= rr; l = r + 1){
            r = min(rr, x / (x / l));
            ans += (r - l + 1) * (x / l);
        }

这样的复杂度是多少呢，其实就是不同的 $\left\lfloor\frac{x}{i}\right\rfloor$ 的个数。
当 $i\leq \sqrt{n}$ 时， $\left\lfloor\frac{x}{i}\right\rfloor$ 最多有 $\sqrt{n}$ 个。
当 $i> \sqrt{n}$ 时， $\left\lfloor\frac{x}{i}\right\rfloor$ 不会超过 $\sqrt{n}$ ，因此最多也只有 $\sqrt{n}$ 个。
因此复杂度是 $O(\sqrt{n})$ 的。
码的好辛苦！！

这题的代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
LL read(){
    LL x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
LL ksm(LL a, LL b, LL p){
    LL s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
LL work(LL num, LL x){
    LL ll, rr, l, r, ans = 0;
    for(int k = 0; k <= 9; k++){
        ll = num * ksm(10, k, 1e18);
        rr = min(x, (num + 1) * ksm(10, k, 1e18) - 1);
        for(l = ll; l <= rr; l = r + 1){
            r = min(rr, x / (x / l));
            ans += (r - l + 1) * (x / l);
        } 
    }
    return ans;
}
int main(){
    LL l, r;
    l = read(); r = read();
    for(int i = 1; i <= 9; i++){
        printf("%lld\n", work(i, r) - work(i, l - 1));
    }
    return 0;
}