前言:这道题自己手写代码是真的有点难写了 qwq 。

思路:我们进行分类讨论。

upd:以下出现的 $a,b,c$ 均为质数。

1. $n \le 10^7-1$ 暴力搜。

2. $n \in [10^7,10^8 - 1]$ 也就是要求 $d(n) = 8$，根据 $d(n) = \prod_{i = 1}(k_i + 1)$，可以知道 $n = abc$ 或者 $n = a^3b$ 或者 $n = a^7$。

3. $n \in [10^8,10^9 - 1]$，$d(n) = 9$，推出 $n = a^8$ 或者 $n = a^2 b^2$。

其实这里面的 $abc$ 都可以暴力枚举，最后存到一个数组里，查询的时候使用二分。

我第一遍 TLE 了，但是我发现 $n \in [10^6, 10^7]$ 好像只有 $1771561$ 和 $4826809$ 两个数，我们把这个特判掉，然后就可以在 2s 左右跑出来。

好像题解都没给代码哎。

#include <bits/stdc++.h>
#define int long long 

using namespace std;
const int N = 3e7 + 5;
int prm[N / 5], tot;
bool isprm[N];
void Init(int lim) {
    for (int i = 2 ; i <= lim ; i ++) {
        if (!isprm[i]) prm[++ tot] = i;
        for (int j = 1 ; j <= tot && prm[j] * i <= lim ; j ++) {
            isprm[prm[j] * i] = 1;
            if (i % prm[j] == 0) break;
        }
    }
}
int d(int x) {
    int u = 1, res = 1;
    while (prm[u] * prm[u] <= x) {
        int s = 1;
        while (x % prm[u] == 0) x /= prm[u], s ++;
        res *= s;
        u ++;
    }
    if (x >= 2) res *= 2;
    return res;
}
int hv(int x) {
    int res = 0;
    while (x) res ++, x /= 10;
    return res;
}
int Ans[N], cnt;
void Donele7() { 
    for (int i = 1 ; i <= 1e6 ; i ++)  
        if (d(i) == hv(i)) Ans[++ cnt] = i;
}
void Done8() {
    // n = a * b * c
    // 1e7 -> 1e8 - 1
    for (int i = 1 ; i <= tot ; i ++) {
        for (int j = i + 1 ; j <= tot ; j ++) {
            if (prm[i] * prm[j] >= 1e8) break;
            for (int k = j + 1 ; k <= tot ; k ++) {
                if (prm[i] * prm[j] * prm[k] >= 1e8) break;
                if (prm[i] * prm[j] * prm[k] >= 1e7) 
                    Ans[++ cnt] = prm[i] * prm[j] * prm[k];
            }
        }
    }
    // n = a * b ^ 3
    for (int i = 1 ; i <= tot ; i ++) {
        int A = prm[i] * prm[i] * prm[i]; 
        if (A >= 1e8) break;
        for (int j = 1 ; j <= tot ; j ++) {
            if (i == j) continue;
            if (A * prm[j] >= 1e8) break;
            if (A * prm[j] >= 1e7) 
                Ans[++ cnt] = A * prm[j];
        }
    }
    // n = b ^ 7
    for (int i = 1 ; i <= tot ; i ++) {
        int u = pow(prm[i], 7);
        if (u >= 1e8) break;
        if (u >= 1e7) Ans[++ cnt] = u;
    }
}
void Done9() {
    // 1e8 -> 1e9 - 1

    // n = a ^ 8
    for (int i = 1 ; i <= tot ; i ++) {
        int u = pow(prm[i], 8);
        if (u >= 1e9) break;
        if (u >= 1e8) Ans[++ cnt] = u;
    }
    // n = a ^ 2 * b ^ 2
    // for (int i = 2 ; i <= tot ; i ++)
    //     for (int j = )
    for (int i = 1 ; i <= tot ; i ++) {
        int A = prm[i] * prm[i];
        for (int j = i + 1 ; j <= tot ; j ++) {
            int B = prm[j] * prm[j];
            if (A * B >= 1e9) break;
            if (A * B >= 1e8) Ans[++ cnt] = A * B;  
        }
    }
}
signed main() {
    // freopen("A.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    Init(3e7);
    // for (int i = 1 ; i <= 10 ; i ++) cout << d(i) << ' ' << hv(i) << '\n';
    // for (int i = 1 ; i <= 10 ; i ++) cout << prm[i] << ' ';
    // cout << '\n';
    Ans[++ cnt] = 1771561;
    Ans[++ cnt] = 4826809;
    Donele7();
    Done8();
    Done9();
    sort(Ans + 1, Ans + cnt + 1);
    cnt = unique(Ans + 1, Ans + cnt + 1) - Ans - 1;
    // cout << cnt << '\n';
    // for (int i = 1 ; i <= cnt ; i ++)
    //     cout << Ans[i] << ' ';
    // cout << '\n';
    int T; cin >> T;
    while (T --) {
        int x, y; cin >> x >> y;
        int L = upper_bound(Ans + 1, Ans + cnt + 1, x - 1) - Ans;
        int R = upper_bound(Ans + 1, Ans + cnt + 1, y) - Ans;
        cout << R - L << '\n';
    }
    return 0;
}

只有我这个螳臂会在二分的时候把 cnt 写成 tot 并且调了一个小时吧。

完结撒花 \o/。