题目题解

问题理解

定义好数为：其所有质因子都至少是两位数（即 $\ge 11$）。
等价地，好数不能被 $2, 3, 5, 7$ 中的任何一个整除。
因为若能被其中某个整除，则它有一个一位数的质因子。

因此，问题转化为：统计区间 $[l, r]$ 中不能被 $2, 3, 5, 7$ 整除的数的个数。

---

第一步：前缀计数技巧

对于区间 $[l, r]$，我们通常计算

$$\text{ans} = \text{count}(r) - \text{count}(l-1),$$

其中 $\text{count}(x)$ 表示 $[1, x]$ 中好数的个数。

---

第二步：解法一 —— 周期性

由于判断条件只依赖于模 $2,3,5,7$ 的余数，而它们的最小公倍数为

$$L = 2 \cdot 3 \cdot 5 \cdot 7 = 210.$$

因此，好数在模 $210$ 下具有周期性：
若 $x$ 是好数，则 $x + 210$ 也是好数。

我们可以预处理 $[0, 209]$ 中的好数个数，记为 good[0..209]。
则

$$\text{count}(x) = \left\lfloor \frac{x}{210} \right\rfloor \cdot \text{good\_count\_in\_one\_period} + \text{good\_count\_in\_remainder}(x \bmod 210). $$

这里 $\text{good\_count\_in\_one\_period} = \sum_{i=0}^{209} [\text{good}(i)]$。

---

第三步：解法二 —— 容斥原理

设 $S_2, S_3, S_5, S_7$ 分别表示 $[1, x]$ 中能被 $2,3,5,7$ 整除的数的集合。
我们要求的是不在任何 $S_i$ 中的数的个数，即

$$\text{count}(x) = x - |S_2 \cup S_3 \cup S_5 \cup S_7|. $$

由容斥原理：

$$\begin{aligned} |S_2 \cup S_3 \cup S_5 \cup S_7| &= |S_2| + |S_3| + |S_5| + |S_7| \\ &\quad - (|S_2 \cap S_3| + |S_2 \cap S_5| + |S_2 \cap S_7| + |S_3 \cap S_5| + |S_3 \cap S_7| + |S_5 \cap S_7|) \\ &\quad + (|S_2 \cap S_3 \cap S_5| + |S_2 \cap S_3 \cap S_7| + |S_2 \cap S_5 \cap S_7| + |S_3 \cap S_5 \cap S_7|) \\ &\quad - |S_2 \cap S_3 \cap S_5 \cap S_7|. \end{aligned} $$

而 $|S_i| = \left\lfloor \frac{x}{i} \right\rfloor$，$|S_i \cap S_j| = \left\lfloor \frac{x}{\mathrm{lcm}(i,j)} \right\rfloor$，等等。
由于 $2,3,5,7$ 两两互质，$\mathrm{lcm}$ 就是它们的乘积。

因此，我们可以用位掩码枚举所有非空子集，对每个子集计算乘积 $m$，并交替加减：

$$\text{count}(x) = \sum_{\text{mask}=0}^{15} (-1)^{\text{popcount(mask)}} \cdot \left\lfloor \frac{x}{m} \right\rfloor, $$

其中 $m$ 是对应 mask 中素数的乘积（mask=0 时 $m=1$，贡献为 $x$）。

---

第四步：时间复杂度

• 解法一：预处理 $O(L)$，每次查询 $O(1)$。
• 解法二：每次查询 $O(2^P) = O(16)$，其中 $P=4$。

两者都满足 $t \le 10^3$，$x \le 10^{18}$。

---

代码实现

解法一（周期性）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool good(int x) {
    return x % 2 != 0 && x % 3 != 0 && x % 5 != 0 && x % 7 != 0;
}

const int L = 210;
int good_in_period[L];

void precompute() {
    for (int i = 0; i < L; i++) {
        good_in_period[i] = good(i);
    }
}

ll count(ll x) {
    if (x < 0) return 0;
    ll full = x / L;
    ll rem = x % L;
    ll cnt_full = 0;
    for (int i = 0; i < L; i++) {
        cnt_full += good_in_period[i];
    }
    ll cnt_rem = 0;
    for (int i = 0; i <= rem; i++) {
        cnt_rem += good_in_period[i];
    }
    return full * cnt_full + cnt_rem;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();
    int t;
    cin >> t;
    while (t--) {
        ll l, r;
        cin >> l >> r;
        cout << count(r) - count(l - 1) << '\n';
    }
    return 0;
}

解法二（容斥原理）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll count(ll x) {
    if (x < 0) return 0;
    ll res = 0;
    int primes[] = {2, 3, 5, 7};
    for (int mask = 0; mask < 16; mask++) {
        ll m = 1;
        int bits = 0;
        for (int i = 0; i < 4; i++) {
            if (mask >> i & 1) {
                m *= primes[i];
                bits++;
            }
        }
        if (bits % 2 == 0) {
            res += x / m;
        } else {
            res -= x / m;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll l, r;
        cin >> l >> r;
        cout << count(r) - count(l - 1) << '\n';
    }
    return 0;
}

---

验证样例

输入：

4
2 100
2 1000
13 37
2 1000000000000000000

输出：

21
227
7
228571428571428570

与题目输出一致。

---

总结

本题的关键在于：

1. 将“好数”等价为不能被 $2,3,5,7$ 整除的数。
2. 利用模 $210$ 的周期性，或容斥原理，快速统计前缀中的好数个数。
3. 用前缀和作差得到区间答案。