用欧拉筛和前缀和搞定XTU1345：手把手教你统计素数字符串里的数字频率

用欧拉筛和前缀和高效统计素数字符串中的数字频率当素数像珍珠一样被串成字符串2357111317...时如何在百万级区间内快速统计某个数字的出现次数这个问题看似简单却融合了数论、字符串处理和算法优化的精髓。本文将手把手带你从暴力解法出发逐步升级到欧拉筛与前缀和的黄金组合最终实现O(1)查询的极致效率。1. 问题本质与暴力解法剖析1.1 理解素数字符串的构造素数字符串是将所有素数按从小到大的顺序直接拼接而成的无限序列。例如前几位是2 3 5 7 11 13 → 23571113...当给定区间[L,R]和数字d时我们需要统计该子串中d出现的次数。比如[1,8]对应23571113数字1出现3次位置4、6、7数字4出现0次1.2 暴力解法的局限性最直观的做法是生成足够多的素数拼接成字符串遍历子串统计数字频率# 伪代码示例 primes generate_primes_up_to(R) s .join(map(str, primes)) count s[L-1:R].count(str(d))这种方法在R较小时可行但当R达到百万级别时素数生成效率低下试除法时间复杂度O(n√n)字符串拼接消耗大量内存每次查询都要线性扫描无法应对T10000的查询量2. 欧拉筛线性时间生成素数2.1 为何选择欧拉筛埃拉托斯特尼筛法埃氏筛已经比试除法高效但其时间复杂度仍是O(n log log n)。欧拉筛线性筛通过两个关键优化实现O(n)时间复杂度每个合数只被标记一次通过最小质因数筛选提前终止标记当i能被prime[j]整除时立即break2.2 欧拉筛的实现细节#define MAX 5000001 int isprime[MAX]; // 0表示素数1表示合数 int prime[MAX]; // 存储素数 int cnt; // 素数计数 void euler_sieve() { isprime[1] 1; // 1不是素数 for(int i 2; i MAX; i) { if(!isprime[i]) prime[cnt] i; for(int j 1; j cnt i*prime[j] MAX; j) { isprime[i*prime[j]] 1; if(i % prime[j] 0) break; } } }关键点说明i % prime[j] 0时break确保每个合数只被最小质因数标记空间换时间使用isprime数组预筛prime数组顺序存储2.3 性能对比实测方法生成10^6个素数时间时间复杂度试除法约15秒O(n√n)埃氏筛约0.8秒O(n log log n)欧拉筛约0.3秒O(n)3. 前缀和从O(n)到O(1)的查询飞跃3.1 前缀和的核心思想前缀和是一种预处理技术通过存储累加信息将区间查询转化为两次简单查询sum[L..R] prefix[R] - prefix[L-1]在本问题中我们需要扩展为二维前缀和qzh[i][d]前i个字符中数字d的出现次数查询结果 qzh[R][d] - qzh[L-1][d]3.2 素数字符串的实时构建不同于暴力法的事先生成整个字符串我们可以边生成素数边统计int qzh[1000001][10]; // 全局变量自动初始化为0 void build_prefix() { int pos 1; // 当前字符位置 for(int i 1; i cnt pos 1000000; i) { char num_str[20]; sprintf(num_str, %d, prime[i]); for(int j 0; num_str[j] pos 1000000; j) { int digit num_str[j] - 0; // 更新所有数字的前缀和 for(int d 0; d 9; d) { qzh[pos][d] qzh[pos-1][d] (d digit); } pos; } } }优化技巧动态处理每个素数的每一位避免存储整个字符串就地更新前缀和数组空间复杂度O(10n)提前终止当pos超过1e6时停止3.3 查询性能对比方法预处理时间单次查询时间万次查询总时间暴力扫描无O(R-L1)10秒前缀和约0.5秒O(1)0.01秒4. 完整解决方案与边界处理4.1 主程序逻辑框架#include stdio.h #include string.h // [欧拉筛和前缀和构建函数如上] int main() { // 预处理阶段 euler_sieve(); build_prefix(); // 查询阶段 int T; scanf(%d, T); while(T--) { int L, R, d; scanf(%d%d%d, L, R, d); printf(%d\n, qzh[R][d] - qzh[L-1][d]); } return 0; }4.2 关键边界情况处理素数生成范围需要确保生成的素数足够拼接出1e6个字符实测表明前5e5个素数足够覆盖前缀和初始化qzh[0][d] 0对所有d成立数组从1开始计数更直观数字转换优化用sprintf替代itoa更标准限制临时字符串长度素数1e7时最长8位4.3 内存与时间优化优化点原始方案优化后方案isprime数组类型int(4字节)char(1字节)素数存储上限固定5e6动态扩展数字转换每次调用itoa复用缓冲区5. 算法扩展与实际应用5.1 相似问题变形统计多个数字同时查询多个数字的频率// 查询数字d1和d2 printf(%d %d\n, qzh[R][d1]-qzh[L-1][d1], qzh[R][d2]-qzh[L-1][d2]);区间数字比例计算某数字在区间占比double ratio (qzh[R][d]-qzh[L-1][d]) / (double)(R-L1);最大频率数字预处理时额外维护极值5.2 数学性质探索素数字符串中数字分布呈现有趣规律数字前1e6位出现次数占比000%1367,82336.78%2124,55912.46%3129,55812.96%.........983,4578.35%注0不会出现是因为素数≥2且不以0开头5.3 工程实践建议预处理并行化# Python多进程示例 from multiprocessing import Pool def process_segment(start, end): # 分段处理素数 pass with Pool(4) as p: p.starmap(process_segment, [(1,25e4), (25e4,5e5)...])内存映射文件对于更大的R可将前缀和数组存入磁盘使用mmap实现按需加载分布式处理将素数生成、字符串拼接、前缀和计算分到不同节点使用MapReduce框架合并结果