约数个数和定理
我们记 d ( i ) d(i) d ( i ) 为 数 i i i 的约数个数,存在等式
∑ i = 1 n d ( i ) = ∑ i = 1 n ⌊ n i ⌋ \sum\limits^{n}_{i = 1}d(i) = \sum\limits^{n}_{i = 1}\left\lfloor \frac{n}{i} \right\rfloor i = 1 ∑ n d ( i ) = i = 1 ∑ n ⌊ i n ⌋
这个等式的证明如下
记二重计数集合 S = { ( a , b ) ∈ Z ≥ 1 2 : a b ≤ n } S = \{(a,b) \in \mathbb{Z}{}^{2}_{\geq1}: ab \leq n\} S = {( a , b ) ∈ Z ≥ 1 2 : ab ≤ n }
含义为两个大于1的正整数a , b a,b a , b 其乘积小于等于n n n 我们需要得知的即为∣ S ∣ |S| ∣ S ∣
按积分组 角度
对于每一个i ∈ [ 1 , n ] i \in [1,n] i ∈ [ 1 , n ] ,将所有满足 a b = i ab = i ab = i 的有序对计入S S S ,这个有序对个数正好就是d ( i ) d(i) d ( i ) ,将i = 1 i = 1 i = 1 到n n n 累加有:
∣ S ∣ = ∑ i = 1 n d ( i ) (1) |S| = \sum\limits^{n}_{i=1}d(i) \tag{1} ∣ S ∣ = i = 1 ∑ n d ( i ) ( 1 )
按固定的a a a 角度
固定
a ∈ [ 1 , n ] a \in [1,n] a ∈ [ 1 , n ] ,则满足条件的
b b b 的个数是满足
a b ≤ n ab \leq n ab ≤ n 的个数,即:
{ b ∣ b ≥ 1 and b ≤ n a } = ⌊ n a ⌋ \{b | b \geq1 \text{ and } b \leq \frac{n}{a}\} = \left\lfloor \frac{n}{a} \right\rfloor { b ∣ b ≥ 1 and b ≤ a n } = ⌊ a n ⌋
累加有:
∣ S ∣ = ∑ a = 1 n ⌊ n a ⌋ (2) |S| = \sum\limits^{n}_{a=1} \left\lfloor \frac{n}{a} \right\rfloor \tag{2} ∣ S ∣ = a = 1 ∑ n ⌊ a n ⌋ ( 2 )
而这两个计数的是同一个集合,结合( 1 ) , ( 2 ) (1),(2) ( 1 ) , ( 2 ) 可证
∑ i = 1 n d ( i ) = ∑ i = 1 n ⌊ n i ⌋ \boxed{\sum\limits^{n}_{i = 1}d(i) = \sum\limits^{n}_{i = 1}\left\lfloor \frac{n}{i} \right\rfloor} i = 1 ∑ n d ( i ) = i = 1 ∑ n ⌊ i n ⌋
Solution1
void solve ()
{
i64 n ;
cin >> n ;
i64 ans = 0 ;
// 注意for中 l 应该是 跳入到下一个块中
for ( i64 l = 1 , r ; l <= n ; l = r + 1 ) {
// 当前一个区间的整除数
i64 k = n / l ;
// 计算块右边界
r = n / k ;
// 计算结果(不要忘记块长)
ans += k * ( r - l + 1 );
}
cout << ans << endl ;
} cpp 换行 复制