2022-07-19: all factors of F (I): I are added up after each factor is squared. For example, f (10) = 1 square + 2 square + 5 square + 10 square = 1 + 4 + 25 + 100 = 130.

2022-07-19：f(i) : i All the factors of , Every factor is squared , Add up .
such as f(10) = 1 square + 2 square + 5 square + 10 square = 1 + 4 + 25 + 100 = 130.
Give a number n, seek f(1) + f(2) + … + f(n).
n <= 10 Of 9 Power .
O(n) All methods will timeout ！ Below it ！
O( Radical sign N) Methods , It's over , A train of thought .
O(log N) Methods ,
From the Blue Bridge Cup exercises .

answer 2022-07-19：

Observation table , Dichotomy .
Time complexity O( Square root N + Square root N * logN).

The code to use rust To write . The code is as follows ：

fn main() {
    
    println!(" Beginning of the test ");
    for i in 1..1000 {
    
        if sum1(i) != sum2(i) {
    
            println!(" Something went wrong {}", i);
        }
    }
    println!(" End of test ");
}

//  Violence method 
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;
}

//  Formal approach 
//  Time complexity O( Square root N +  Square root 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);
    }
    //  The second half 
    //  Give you a number , Two points out several factors , At this number ！
    //  By the maximum number ( Radical sign N),  Start two 
    let mut k = n / (sqrt + 1);
    while k >= 1 {
    
        ans += sum_of_limit_number(n, k);
        k -= 1;
    }
    return ans;
}

//  Sum of squares formula 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;
}

The results are as follows ：

---

Zuo Shen java Code