UVa 12039 Goldbach‘s Cardinality

题目描述Goldbach’s Cardinality\texttt{Goldbachs Cardinality}Goldbach’s Cardinality哥德巴赫基数GC(n)\textit{GC}(n)GC(n)定义为偶数nnn能够表示为两个不同素数之和的不同方式数。例如307231119131730 7 23 11 19 13 173072311191317因此GC(30)3\textit{GC}(30) 3GC(30)3。本题要求对给定的区间[low,high][\textit{low}, \textit{high}][low,high]计算该区间内所有偶数的哥德巴赫基数之和即∑m2m∈[low,high]GC(2m) \sum_{\substack{m \\ 2m \in [\textit{low}, \textit{high}]}} \textit{GC}(2m)m2m∈[low,high]​∑​GC(2m)输入格式输入包含多行每行两个整数low\textit{low}low和high\textit{high}high满足0low≤high≤1070 \textit{low} \le \textit{high} \le 10^70low≤high≤107。输入以一行0 0结束该行不作处理。数据规模约200020002000组查询。输出格式对于每组查询输出一行一个整数表示区间[low,high][\textit{low}, \textit{high}][low,high]内所有偶数的哥德巴赫基数之和。样例输入10 20 30 40 0 0输出9 16题目分析直接对每个偶数分别计算GC\textit{GC}GC是不可行的因为单个偶数GC\textit{GC}GC的计算需要遍历素数表而区间长度可能很大且查询数量较多。我们设T(x)∑m1xGC(2m) T(x) \sum_{m1}^{x} \textit{GC}(2m)T(x)m1∑x​GC(2m)那么区间[low,high][\textit{low}, \textit{high}][low,high]的答案即为T(⌊high2⌋)−T(⌈low2⌉−1) T\left(\left\lfloor \frac{\textit{high}}{2} \right\rfloor\right) - T\left(\left\lceil \frac{\textit{low}}{2} \right\rceil - 1\right)T(⌊2high​⌋)−T(⌈2low​⌉−1)问题转化为对于给定的xxx如何高效计算T(x)T(x)T(x)。交换求和次序T(x)T(x)T(x)等于所有满足以下条件的素数对(p,q)(p, q)(p,q)的个数ppp和qqq均为素数pqp qpq保证两个素数不同且每个拆分只计一次pq≤2xp q \le 2xpq≤2x。由于偶数2m2m2m的拆分为两个素数之和且两个素数不同那么它们必然一奇一偶或两奇。但偶素数只有222若其中一个为222则另一个必为奇数其和为奇数不可能等于偶数2m2m2m若两数均为222则224224224但两个素数相同不符合“不同”的要求。因此所有有效拆分中的素数均为奇素数素数222完全不参与。因此对于固定的奇素数ppp且pxp xpx满足pq≤2x−pp q \le 2x - ppq≤2x−p的素数qqq的个数为π(2x−p)−π(p) \pi(2x - p) - \pi(p)π(2x−p)−π(p)其中π(n)\pi(n)π(n)表示不超过nnn的素数个数。于是T(x)∑p∈Ppxp≠2(π(2x−p)−π(p)) T(x) \sum_{\substack{p \in \mathbb{P} \\ p x \\ p \ne 2}} \bigl( \pi(2x - p) - \pi(p) \bigr)T(x)p∈Ppxp2​∑​(π(2x−p)−π(p))解题思路预处理素数表及前缀计数由于high≤107\textit{high} \le 10^7high≤107我们可以在程序开始前一次性使用埃氏筛或线性筛得到111到10710^7107的所有素数同时构造前缀素数计数数组π\piπ其中π[i]\pi[i]π[i]表示不超过iii的素数个数。计算T(x)T(x)T(x)对于每个xxx我们只需遍历所有小于xxx的奇素数ppp用π\piπ数组以O(1)O(1)O(1)时间得到差值并累加。单次T(x)T(x)T(x)的时间复杂度为O(π(x))O(\pi(x))O(π(x))其中π(5×106)≈3.5×105\pi(5\times 10^6) \approx 3.5\times 10^5π(5×106)≈3.5×105。若对每个查询都直接计算最坏情况下2000×3.5×105≈7×1082000 \times 3.5\times 10^5 \approx 7\times 10^82000×3.5×105≈7×108次操作在 C 优化下可以接受。但为了进一步提高效率我们使用哈希表缓存已经计算过的xxx避免重复计算因为输入中可能存在相同的xxx。区间答案计算对每组查询令L⌈low2⌉⌊low12⌋,R⌊high2⌋ L \left\lceil \frac{\textit{low}}{2} \right\rceil \left\lfloor \frac{\textit{low}1}{2} \right\rfloor, \quad R \left\lfloor \frac{\textit{high}}{2} \right\rfloorL⌈2low​⌉⌊2low1​⌋,R⌊2high​⌋则答案为T(R)−T(L−1) T(R) - T(L-1)T(R)−T(L−1)若L−13L-1 3L−13则T(L−1)0T(L-1) 0T(L−1)0。复杂度分析预处理筛法O(Nlog⁡log⁡N)O(N \log \log N)O(NloglogN)其中N107N 10^7N107。每次计算T(x)T(x)T(x)遍历所有小于xxx的奇素数均摊后总操作次数约为O(查询数×π(max⁡R))O(\text{查询数} \times \pi(\max R))O(查询数×π(maxR))。加上缓存实际运行效率良好。空间复杂度O(N)O(N)O(N)存储素数表和π\piπ数组。代码实现// Goldbachs Cardinality// UVa ID: 12039// Verdict: Accepted// Submission Date: 2026-06-22// UVa Run Time: 0.590s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN10000000;vectorintprimes;vectorintpiCnt;// piCnt[i] 素数个数 ≤ ivectorcharisPrime;// 埃氏筛voidsieve(intn){isPrime.assign(n1,true);if(n0)isPrime[0]false;if(n1)isPrime[1]false;for(inti2;i*in;i){if(isPrime[i]){for(intji*i;jn;ji)isPrime[j]false;}}primes.clear();for(inti2;in;i)if(isPrime[i])primes.push_back(i);piCnt.assign(n1,0);for(inti2;in;i)piCnt[i]piCnt[i-1](isPrime[i]?1:0);}// 计算 T(x) sum_{m1}^{x} GC(2m)// 枚举所有奇素数 p (p x)累加 piCnt[2x-p] - piCnt[p]longlongcalcT(intx){if(x3)return0;longlongres0;// 从索引 1 开始跳过 primes[0] 2for(inti1;i(int)primes.size()primes[i]x;i){intpprimes[i];respiCnt[2*x-p]-piCnt[p];}returnres;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);vectorpairint,intqueries;intlow,high,maxHigh0;while(cinlowhigh){if(low0high0)break;queries.push_back({low,high});if(highmaxHigh)maxHighhigh;}if(queries.empty())return0;sieve(maxHigh);unordered_mapint,longlongcache;for(autoq:queries){intlowq.first,highq.second;intL(low1)/2;// ceil(low/2)intRhigh/2;longlongsumR,sumLm1;autoitRcache.find(R);if(itR!cache.end())sumRitR-second;else{sumRcalcT(R);cache[R]sumR;}intleftL-1;autoitLcache.find(left);if(itL!cache.end())sumLm1itL-second;else{sumLm1calcT(left);cache[left]sumLm1;}coutsumR-sumLm1\n;}return0;}总结本题的核心是将区间查询转化为前缀和形式并利用素数筛法和前缀素数计数快速计算每个前缀的哥德巴赫基数累积和。关键技巧点排除素数222由于有效拆分的两个素数必须不同且和为偶数素数222不可能出现在任何有效拆分中因此枚举时跳过222能保证正确性并减少计算量。前缀和转化通过定义T(x)T(x)T(x)将区间求和问题转化为两个前缀函数值的差避免了逐偶数计算。缓存优化对相同xxx的T(x)T(x)T(x)计算结果进行缓存有效减少了重复计算提高了多组查询下的整体效率。该算法在10710^7107的数据范围内运行良好体现了预处理 数学化简 缓存优化的综合应用思路。