题目描述给定XXX和YYY1≤X≤Y≤1051 \le X \le Y \le 10^51≤X≤Y≤105求三条边长均为整数且在[X,Y][X, Y][X,Y]内的不同三角形个数。三角形无序满足较小两边之和大于第三边。输入格式第一行整数TTT1≤T≤2×1041 \le T \le 2\times 10^41≤T≤2×104接下来TTT行每行两个整数X,YX, YX,Y。输出格式对于每个测试用例输出一行答案。样例输入5 1 10 5 10 5 15 10 20 100 400输出125 55 252 285 3898600题目分析直接枚举三边不可行。固定最大边ccc设a≤b≤ca \le b \le ca≤b≤c满足abcabcabc。记f(c)f(c)f(c)为以ccc为最大边的三角形数答案即∑cXYf(c)\sum_{cX}^{Y} f(c)∑cXYf(c)。我们需要对f(c)f(c)f(c)分段化简用等差数列和平方和公式O(1)O(1)O(1)累加。解题思路令LXL XLXRYR YRY。对于固定ccc分情况c≤2L−3c \le 2L-3c≤2L−3此时所有满足L≤a≤b≤cL \le a \le b \le cL≤a≤b≤c的无序对均构成三角形f(c)(c−L1)(c−L2)2f(c) \frac{(c-L1)(c-L2)}{2}f(c)2(c−L1)(c−L2)。令nc−L1n c-L1nc−L1则该段对答案的贡献为∑n1Nn(n1)2(N23)\sum_{n1}^{N} \frac{n(n1)}{2} \binom{N2}{3}∑n1N2n(n1)(3N2)其中Nmin(R,2L−3)−L1N \min(R, 2L-3) - L 1Nmin(R,2L−3)−L1仅当L≥3L \ge 3L≥3。c∈[2L−2,2L]c \in [2L-2, 2L]c∈[2L−2,2L]此区间最多包含333个ccc直接计算f(c)f(c)f(c)并累加。c≥2L1c \ge 2L1c≥2L1令k⌊c/2⌋k \lfloor c/2 \rfloork⌊c/2⌋。若c2kc 2kc2k偶数则f(2k)k2k−L(L−1)2f(2k) k^2 k - \frac{L(L-1)}{2}f(2k)k2k−2L(L−1)其中k≥Lk \ge Lk≥L。若c2k1c 2k1c2k1奇数则f(2k1)k22k−L2−L−22f(2k1) k^2 2k - \frac{L^2-L-2}{2}f(2k1)k22k−2L2−L−2其中k≥Lk \ge Lk≥L。对kkk在对应区间内求和利用∑k\sum k∑k和∑k2\sum k^2∑k2公式即可。上述分段涵盖了所有ccc且每段均可O(1)O(1)O(1)计算总复杂度O(T)O(T)O(T)。代码实现// Triangle// UVa ID: 11866// Verdict: Accepted// Submission Date: 2026-06-21// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;longlongsumSq(intd1,intd2){if(d1d2)return0;autof[](intn)-longlong{return1LL*n*(n1)*(2*n1)/6;};returnf(d2)-f(d1-1);}longlongcountTriangles(intL,intR){longlongans0;// 区间 A: c ∈ [L, min(R, 2L-3)]if(L3){inthighAmin(R,2*L-3);if(highAL){intThighA-L1;ans1LL*(T2)*(T1)*T/6;// C(T2,3)}}// 区间 B: c ∈ [max(L, 2L-2), min(R, 2L)]最多三个值intlowBmax(L,2*L-2);inthighBmin(R,2*L);for(intclowB;chighB;c){intB0c/21;longlongnc-B01;ans1LL*(B0c)*n/2(1LL-L)*n;}// 区间 C: c ∈ [max(L, 2L1), R]intlowCmax(L,2*L1);inthighCR;if(lowChighC){// 偶数 c 2kintkStartEvenmax((lowC1)/2,L1);intkEndEvenhighC/2;if(kStartEvenkEndEven){intd1kStartEven-L,d2kEndEven-L;longlongnd2-d11;longlongsumD1LL*(d1d2)*n/2;longlongsumD2sumSq(d1,d2);anssumD2(2LL*L1)*sumD1LL*L*(L3)/2*n;}// 奇数 c 2k1intkStartOddmax(lowC/2,L);intkEndOdd(highC-1)/2;if(kStartOddkEndOdd){intd1kStartOdd-L,d2kEndOdd-L;longlongnd2-d11;longlongsumD1LL*(d1d2)*n/2;longlongsumD2sumSq(d1,d2);anssumD2(2LL*L2)*sumD(1LL*L*(L5)/21)*n;}}returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intX,Y;cinXY;coutcountTriangles(X,Y)\n;}return0;}总结本题利用固定最大边并分段求和将O(Y)O(Y)O(Y)的枚举优化为O(1)O(1)O(1)数学计算。核心技巧是分类讨论ccc与2L2L2L的关系分别用组合数或平方和公式累加。注意使用long long防止溢出并处理好边界条件如LLL较小时。这种化枚举为公式的思路在区间计数问题中非常实用。
