f(i) : i的所有因子，每个因子都平方之后，累加起来。
比如f(10) = 1平方 + 2平方 + 5平方 + 10平方 = 1 + 4 + 25 + 100 = 130。
给定一个数n，求f(1) + f(2) + … + f(n)。
n <= 10的9次方。
O(n)的方法都会超时！低于它的！
O(根号N)的方法，就过了，一个思路。
O(log N)的方法，
观察表，二分法。
时间复杂度O(开平方根N + 开平方根N * logN)。
代码用rust编写。代码如下：
fn main() {
println!("测试开始");
for i in 1..1000 {
if sum1(i) != sum2(i) {
println!("出错了{}", i);
}
}
println!("测试结束");
}
// 暴力方法
fn sum1(n: i64) -> i64 {
let mut cnt: Vec<i64> = vec![];
for _ in 0..n + 1 {
cnt.push(0);
}
for num in 1..=n {
for j in 1..=num {
if num % j == 0 {
cnt[j as usize] += 1;
}
}
}
let mut ans = 0;
for i in 1..=n {
ans += i * i * cnt[i as usize];
}
return ans;
}
fn get_sqrt(n: i64) -> i64 {
let mut l: i64 = 1;
let mut r = n;
let mut m: i64;
let mut mm: i64;
let mut ans = 1;
while l <= r {
m = l + ((r - l) >> 1);
mm = m * m;
if mm == n {
return m;
} else if mm < n {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
// 正式方法
// 时间复杂度O(开平方根N + 开平方根N * logN)
fn sum2(n: i64) -> i64 {
// 100 -> 10
// 200 -> 14
let sqrt = get_sqrt(n);
let mut ans = 0;
for i in 1..=sqrt {
ans += i * i * (n / i);
}
// 后半段
// 给你一个个数，二分出几个因子，处在这个个数上！
// 由最大个数(根号N), 开始二分
let mut k = n / (sqrt + 1);
while k >= 1 {
ans += sum_of_limit_number(n, k);
k -= 1;
}
return ans;
}
// 平方和公式n(n+1)(2n+1)/6
fn sum_of_limit_number(v: i64, n: i64) -> i64 {
let r = cover(v, n);
let l = cover(v, n + 1);
return ((r * (r + 1) * ((r << 1) + 1) - l * (l + 1) * ((l << 1) + 1)) * n) / 6;
}
fn cover(v: i64, n: i64) -> i64 {
let mut l = 1;
let mut r = v;
let mut m;
let mut ans = 0;
while l <= r {
m = (l + r) / 2;
if m * n <= v {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}执行结果如下：
