题目分析

题目要求我们找出给定区间 ([x_L, x_H]) 内的所有“爆炸性数字”。爆炸性数字的定义为：

• 可以表示为 (x = p_0 \cdot p_1 \cdot p_2 \cdot \ldots \cdot p_n)，其中 (p_0 = 1)，其余 (p_i) 是不同的质数。
• 存在整数 (A) 和 (B)，使得 (p_i = A \cdot p_{i-1} + B)（(i = 1, 2, \ldots, n)）。
• 序列长度 (n \geq 3)。

解题思路

1. 生成质数序列：从 (p_0 = 1) 开始，根据递推关系 (p_i = A \cdot p_{i-1} + B) 生成后续质数。
2. 枚举参数：枚举可能的 (A) 和 (B) 的值，生成符合条件的质数序列。
3. 检查乘积：计算序列的乘积 (x)，并检查是否在给定范围内。
4. 去重与统计：确保每个爆炸性数字只被统计一次，并输出结果。

实现步骤

1. 质数判断：实现一个高效的质数判断函数 isPrime。
2. 生成序列：对于每个可能的 (A) 和 (B)，生成质数序列并检查其乘积是否在范围内。
3. 范围检查：确保生成的乘积 (x) 在 ([x_L, x_H]) 内。
4. 统计结果：使用集合去重，并统计符合条件的数字数量。

优化思路

• 限制参数范围：(A) 和 (B) 的取值范围不宜过大，否则会导致计算量剧增。
• 提前终止：如果生成的乘积 (x) 超过 (x_H)，可以提前终止当前序列的生成。
• 预处理质数：可以预处理一定范围内的质数，加快质数判断速度。

代码实现

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long LL;

// 判断一个数是否为质数
bool isPrime(LL n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    LL max_div = static_cast<LL>(sqrt(n)) + 1;
    for (LL i = 3; i <= max_div; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// 计算范围内的爆炸数数量
int countExplosiveNumbers(LL xL, LL xH) {
    int count = 0;
    
    // 枚举可能的初始质数p0
    for (LL p0 = 2; p0 <= 1000; ++p0) {
        if (!isPrime(p0)) continue;
        
        // 枚举可能的A值
        for (LL A = 1; A <= 100; ++A) {
            // 生成数列并检查
            vector<LL> primes;
            primes.push_back(p0);
            
            LL current = p0;
            bool valid = true;
            
            // 生成最多6个质数的序列
            for (int i = 1; i <= 5; ++i) {
                // 计算B = p1 - A*p0
                LL B = primes[1] - A * primes[0];
                
                // 计算下一个质数
                LL next = A * current + B;
                if (next <= current || !isPrime(next)) {
                    valid = false;
                    break;
                }
                
                primes.push_back(next);
                current = next;
                
                // 检查当前乘积是否超出范围
                LL product = 1;
                bool overflow = false;
                
                // 使用传统for循环替代范围for循环(C++98不支持)
                for (vector<LL>::iterator it = primes.begin(); it != primes.end(); ++it) {
                    LL p = *it;
                    if (product > (xH + p - 1) / p) {
                        overflow = true;
                        break;
                    }
                    product *= p;
                }
                
                if (overflow) break;
                
                // 检查乘积是否在范围内
                if (product >= xL && product <= xH) {
                    ++count;
                }
            }
        }
    }
    
    return count;
}

int main() {
    int N;
    cin >> N;
    
    for (int i = 0; i < N; ++i) {
        LL xL, xH;
        cin >> xL >> xH;
        
        // 处理特殊情况
        if (xL > xH) {
            cout << 0 << endl;
            continue;
        }
        
        cout << countExplosiveNumbers(xL, xH) << endl;
    }
    
    return 0;
}