区间因数个数之和时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述对于给定的l , r l, rl,r求值在l ∼ r l \sim rl∼r之间的所有整数的因数个数之和形式化的求∑ i l r ∑ d ∣ i 1 \sum_{il}^{r} \sum_{d \mid i} 1∑ilr​∑d∣i​1的值。输入描述输入包含一行两个整数l , r ( 1 ≤ l ≤ r ≤ 10 12 ) l, r\ (1 \le l \le r \le 10^{12})l,r(1≤l≤r≤1012)。输出描述输出一行一个整数代表l ∼ r l \sim rl∼r中所有数的因数个数之和。示例 1输入2 5输出9示例 2输入555 666输出852解题思路本题是数论中因子个数求和的经典问题。要求计算区间[ l , r ] [l, r][l,r]内所有整数的因子个数之和即∑ i l r d ( i ) \sum_{il}^{r} d(i)∑ilr​d(i)其中d ( i ) d(i)d(i)表示i ii的因子个数。由于r rr可达10 12 10^{12}1012不能直接枚举每个数求因子需要利用前缀和与数论分块/对称性优化。1. 问题等价转化设S ( n ) ∑ i 1 n d ( i ) S(n) \sum_{i1}^{n} d(i)S(n)∑i1n​d(i)则答案 S ( r ) − S ( l − 1 ) S(r) - S(l-1)S(r)−S(l−1)。交换求和顺序S ( n ) ∑ i 1 n ∑ d ∣ i 1 ∑ d 1 n ⌊ n d ⌋ S(n) \sum_{i1}^{n} \sum_{d|i} 1 \sum_{d1}^{n} \left\lfloor \frac{n}{d} \right\rfloorS(n)i1∑n​d∣i∑​1d1∑n​⌊dn​⌋即S ( n ) S(n)S(n)等于所有d ∈ [ 1 , n ] d \in [1,n]d∈[1,n]在1 ∼ n 1\sim n1∼n中作为因子出现的总次数之和。目标转化为快速计算F ( n ) ∑ d 1 n ⌊ n / d ⌋ F(n) \sum_{d1}^{n} \lfloor n/d \rfloorF(n)∑d1n​⌊n/d⌋。2. 高效计算F ( n ) F(n)F(n)直接枚举d dd需要O ( n ) O(n)O(n)不可行。利用⌊ n / d ⌋ \lfloor n/d \rfloor⌊n/d⌋的取值只有O ( n ) O(\sqrt n)O(n​)种可以用数论分块在O ( n ) O(\sqrt n)O(n​)内完成。另一种常用对称公式设q ⌊ n ⌋ q \lfloor \sqrt n \rfloorq⌊n​⌋则F ( n ) 2 ∑ i 1 q ⌊ n i ⌋ − q 2 F(n) 2 \sum_{i1}^{q} \left\lfloor \frac{n}{i} \right\rfloor - q^2F(n)2i1∑q​⌊in​⌋−q2证明所有i ≤ n i \le \sqrt ni≤n​的项⌊ n / i ⌋ \lfloor n/i \rfloor⌊n/i⌋构成前半部分对于i n i \sqrt nin​其值⌊ n / i ⌋ ≤ q \lfloor n/i \rfloor \le q⌊n/i⌋≤q通过对称性可由前半部分覆盖减去重复的q 2 q^2q2。代码中的实现正是基于该公式for(ll i1;iq;i){tn/i-i;// 即 floor(n/i) - irest*21;// 等价于 2*floor(n/i) - 2*i 1}累加后得到2 ∑ i 1 q ⌊ n / i ⌋ − q ( q 1 ) q 2 ∑ i 1 q ⌊ n / i ⌋ − q 2 2\sum_{i1}^q \lfloor n/i \rfloor - q(q1) q 2\sum_{i1}^q \lfloor n/i \rfloor - q^22∑i1q​⌊n/i⌋−q(q1)q2∑i1q​⌊n/i⌋−q2与公式一致。3. 算法步骤读入l , r l, rl,r。定义函数sum(n)计算F ( n ) F(n)F(n)若n ≤ 0 n \le 0n≤0返回0 00。计算q ⌊ n ⌋ q \lfloor \sqrt n \rfloorq⌊n​⌋循环i 1 ∼ q i 1 \sim qi1∼q累加2 × ( ⌊ n / i ⌋ − i ) 1 2 \times (\lfloor n/i \rfloor - i) 12×(⌊n/i⌋−i)1。答案 sum(r) - sum(l-1)输出即可。4. 复杂度分析时间复杂度每次求sum(n)需要O ( n ) O(\sqrt n)O(n​)次循环。r ≤ 10 12 r \le 10^{12}r≤1012r ≈ 10 6 \sqrt r \approx 10^6r​≈106完全可行。空间复杂度O ( 1 ) O(1)O(1)仅使用几个变量。总结将区间因子个数之和转化为前缀和差分利用⌊ n / d ⌋ \lfloor n/d \rfloor⌊n/d⌋的对称性将单次查询优化到O ( n ) O(\sqrt n)O(n​)。方法简单高效适用于10 12 10^{12}1012级别的大范围求和。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llsum(ll n){ll qsqrt(n),t,res0;for(ll i1;iq;i){tn/i-i;rest*21;}returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll l,r;cinlr;cout(sum(r)-sum(l-1))\n;return0;}