题解 | 下取整乘积求和 #

$[模板+数论分块]$

求 $\sum_{i =1}^{n}{i\times \lfloor \frac{n}{i} \rfloor}$ ，有 $\sum_{i =1}^{n}{\lfloor \frac{n}{i} \rfloor}$ 基本可以确定是数论分块了，但还得乘以 $i$

以 $10$ 为例：

$1 \times \lfloor \frac{10}{1} \rfloor = 1 \times 10$

$2 \times \lfloor \frac{10}{2} \rfloor = 2 \times 5$

$3 \times \lfloor \frac{10}{3} \rfloor = 3 \times 3$

$4 \times \lfloor \frac{10}{4} \rfloor = 4 \times 2$

$5 \times \lfloor \frac{10}{5} \rfloor = 5 \times 2$

$6 \times \lfloor \frac{10}{6} \rfloor = 6 \times 1$

$7 \times \lfloor \frac{10}{7} \rfloor = 7 \times 1$

$8 \times \lfloor \frac{10}{8} \rfloor = 8 \times 1$

$9 \times \lfloor \frac{10}{9} \rfloor = 9 \times 1$

$10 \times \lfloor \frac{10}{10} \rfloor = 10\times 1$

注意到每个块的答案贡献是 $\lfloor \frac{n}{l} \rfloor \times \sum_{i = l}^{r}{i}$ ，设这个块的长度为 $len$ ，那么就是 $\lfloor \frac{n}{l} \rfloor \times \frac{(l + (l+len-1))\times len}{2}$

那么就直接用数论分块去累加每个块的答案贡献即可

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n; cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        int l = i, r = (n / (n / i));
        int len = r - l + 1;
        ans += (n / i) * (i + i + len - 1) * len / 2;
        i = r;
    }
    cout << ans << endl;
    return 0;
}