2024寒假每日一题全部题解传送门>>

根据题目数据范围，时间复杂度应控制在$O(\sqrt{n})$以内。如果考虑直接暴力枚举$1$~$n$每个数的因数的话，时间复杂度为$O(n\sqrt{n})$，显然不行，那就再来考虑如何优化。

首先来看看$f(1)$~$f(5)$里面的每个因数数量的分布:
$f(1)=1^2$。
$f(2)=1^2+2^2$。
$f(3)=1^2+3^2$。
$f(4)=1^2+2^2+4^2$。
$f(5)=1^2+5^2$。
可以发现$1=\lfloor \frac{5}{1} \rfloor，2=\lfloor \frac{5}{2} \rfloor，3=\lfloor \frac{5}{3} \rfloor，4=\lfloor \frac{5}{4} \rfloor，5=\lfloor \frac{5}{5} \rfloor$。
故可以得出$\sum\limits_{i=1}^{i=n}f(i)=\sum\limits_{i=1}^{i=n}\lfloor \frac{n}{i} \rfloor i^2$，此时时间复杂度优化到$O(n)$，但对于题目数据还是不太友好，所以还是得继续优化。

首先知道$\sum\limits_{i=1}^{i=n}f(i)$里面的每个因数$1\leq i \leq n$的数量为$\lfloor \frac{n}{i} \rfloor$，可以发现$i$越大，$\lfloor \frac{n}{i} \rfloor$就越小，即因数$i$的数量就越少。又可以进一步发现对于某一段连续因子$i$，$\lfloor \frac{n}{i} \rfloor$的值是相等的，故可以试着将这些数量相等的因数分成一组来算。

例如：$\sum\limits_{i=1}^{i=5}f(i)$里面有$1$个因数$5$，$1$个因数$4$，$1$个因数$3$，$2$个因数$2$， $5$个因数$1$。将因数$1$分成一组，因数$2$分成一组，剩下的因数$3,4,5$分成一组。而此时对于某个分组内的因数肯定是连续的，故可以直接利用平方和公式和前缀和来快速求出这一组的平方和。
注：$\sum\limits_{i=1}^{i=n}i^2=\frac{n(n+1)(2n+1)}{6}$。

假设当前分组内每个因数的个数为$k$个，那么对于这个分组内最大的因数即为$r = \lfloor \frac{n}{k} \rfloor$，这一分组内最小的因数即为上一分组内最大的因数加$1$（因为相邻分组之间的因数是连续的）。假设上一分组每个因数的个数为$k_1$个，那么当前分组内的最小因数即为$l=\lfloor \frac{n}{k_1} \rfloor+1$。那么对于当前分组内的因数求平方和就是$k*(sum(r)-sum(l-1))$。（$sum(x)$表示求$1$~$x$的平方和）

对于每个数$n$，它的因数最多有$2\sqrt{n}$个，故分的组数最多为$2\sqrt{n}$个，而每一组的连续因数的平方和可以用$O(1)$的时间求出来，故总时间复杂度为$O(\sqrt{n})$，这道题目就此解决！其实，这种思路就是数论中的整除分块的思想，感兴趣的可以百度了解一下~

C++代码：

#include<iostream>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7; 
int n;

int qmi(int a, int b) // 快速幂求逆元
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (LL)res * a % MOD;
        b >>= 1;
        a = (LL)a * a % MOD;
    }

    return res;
}

int sum(int x) // 求平方和
{
    return (LL)x * (x + 1) % MOD * (2 * x + 1) % MOD * qmi(6, MOD - 2) % MOD;
}

int main()
{
    scanf("%d", &n);

    // l~r表示因数个数相同的一段连续的因子
    int l = 1, r, res = 0;
    for(int i = 1; i <= n; i = r + 1)
    {
        int cnt = n / i;
        r = n / cnt;
        // 负数取模可能为负，记得加上模数再模一下
        res = ((res + (LL)cnt * (sum(r) - sum(i - 1))) % MOD + MOD) % MOD; 
    }

    printf("%d", res);
    return 0;
}