区间因数个数之和
时间限制：1 秒
空间限制：256 MB
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
对于给定的l , r l, rl,r，求值在l ∼ r l \sim rl∼r之间的所有整数的因数个数之和，形式化的，求∑ i = l r ∑ d ∣ i 1 \sum_{i=l}^{r} \sum_{d \mid i} 1∑i=lr∑d∣i1的值。
输入描述
输入包含一行两个整数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_{i=l}^{r} d(i)∑i=lrd(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_{i=1}^{n} d(i)S(n)=∑i=1nd(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_{i=1}^{n} \sum_{d|i} 1 = \sum_{d=1}^{n} \left\lfloor \frac{n}{d} \right\rfloorS(n)=i=1∑nd∣i∑1=d=1∑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_{d=1}^{n} \lfloor n/d \rfloorF(n)=∑d=1n⌊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_{i=1}^{q} \left\lfloor \frac{n}{i} \right\rfloor - q^2F(n)=2i=1∑q⌊in⌋−q2
证明：所有i ≤ n i \le \sqrt ni≤n的项⌊ n / i ⌋ \lfloor n/i \rfloor⌊n/i⌋构成前半部分；对于i > n i > \sqrt ni>n，其值⌊ n / i ⌋ ≤ q \lfloor n/i \rfloor \le q⌊n/i⌋≤q，通过对称性可由前半部分覆盖，减去重复的q 2 q^2q2。 - 代码中的实现正是基于该公式：
累加后得到2 ∑ i = 1 q ⌊ n / i ⌋ − q ( q + 1 ) + q = 2 ∑ i = 1 q ⌊ n / i ⌋ − q 2 2\sum_{i=1}^q \lfloor n/i \rfloor - q(q+1) + q = 2\sum_{i=1}^q \lfloor n/i \rfloor - q^22∑i=1q⌊n/i⌋−q(q+1)+q=2∑i=1q⌊n/i⌋−q2，与公式一致。for(ll i=1;i<=q;i++){t=n/i-i;// 即 floor(n/i) - ires+=t*2+1;// 等价于 2*floor(n/i) - 2*i + 1}
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 qi=1∼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≤1012，r ≈ 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级别的大范围求和。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llsum(ll n){ll q=sqrt(n),t,res=0;for(ll i=1;i<=q;i++){t=n/i-i;res+=t*2+1;}returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll l,r;cin>>l>>r;cout<<(sum(r)-sum(l-1))<<"\n";return0;}
