题解

观察题目数据范围可知，直接暴力枚举不可行，需要寻找优化解。

题目给定区间 $[L, R]$，要求求出满足 $x \% 71 = 11, x \% 73 = 13$ 且 $x$ 为素数的 $x$ 的个数。这涉及同余方程的一个数学性质：对于任意形式为 $x \% a = c_1, x \% b = c_2$ 的方程组，都存在一个周期 $T$，使得解 $x$ 随周期循环出现。证明过程很简单：假设 $x_1, x_2$ 均满足该同余方程组，且 $x_2 > x_1$，显然有 $(x_2 – x_1) \% a = 0$ 与 $(x_2 – x_1) \% b = 0$。若令周期 $T = x_2 – x_1$，最小正周期即为 $\text{lcm}(a, b)$（即最小公倍数）。

回到本题，循环周期 $T = \text{lcm}(71, 73)$，由于 $71$ 和 $73$ 均为素数，其最小公倍数即为两者乘积 $5183$。通过暴力枚举可以找到满足方程的最小非负整数解 $x_0 = 5123$。由此得出满足同余方程的通解公式：$x = T \times k + x_0 = 5183k + 5123 \ (k \in \mathbb{N})$。

接下来，只需找到区间 $[L, R]$ 中合法的最小 $x’$，再进行步长为 $T$ 的循环。本质上是求通解中使得 $x \ge L$ 的最小 $k$ 值：由 $5183k + 5123 \ge L$，得出 $k \ge \lceil \frac{L – 5123}{5183} \rceil$（符号 $\lceil \dots \rceil$ 表示向上取整）。计算出 $k$ 后带回通解公式，即可得到区间内的起始点 $x’$。随后以 $T = 5183$ 为步长进行 for 循环即可（即每次 i += 5183）。

关于如何使用试除法判断素数：数字的因数是成对出现的。设一数字为 $x$，若它有因数 $a$，则必有另一个因数 $b = \frac{x}{a}$。素数的定义是仅有 $1$ 和它本身两个因数（不包含 $1$）。若 $x$ 在 $(1, x)$ 开区间内存在因数，则 $x$ 不是素数。因为因数是成对出现的，只需检查 $(1, \sqrt{x}]$ 范围即可。若此范围内不存在能整除 $x$ 的数，则 $(1, x)$ 中也必然不存在，这能大幅减少判断次数。

补充一个知识点：时间复杂度。它是用于评估算法运行效率的普适标准。定义虽然复杂，但目前只需记住一点：在常规竞赛环境中，当程序的总循环运算次数超过 $10^8$ 次时，就极有可能超时（TLE）。循环次数的估算相对直观，如果不明白可以在群里交流。

C++

#include <bits/stdc++.h>

using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;

void solve()
{
    int T = 5183;
    int base = 5123;
    int l, r; cin >> l >> r;
    int start = ((l - base + T - 1) / T) * T + base;

    int ans = 0;
    for (int i = start; i <= r; i += T)
    {
        if (i % 2 == 0) continue;

        bool yes = false;
        for (int j = 2; j * j <= i; j++)
        {
            if (i % j == 0)
            {
                yes = true; break;
            }
        }

        if (yes) continue;
        else ans++;
    }

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;

    while (t--)
    {
        solve();
    }
}