2022-07-19：f(i) : i的所有因子，每个因子都平方之后，累加起来。比如f(10) = 1平方

moonfdd 的个人博客 / 0 / 0 / 创建于 2年前

2022-07-19：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) 的方法，
来自蓝桥杯练习题。

答案 2022-07-19：

观察表，二分法。
时间复杂度 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;
}