1.分析对总和的贡献,可以看出每一个因子 $i$ 的出现次数为$\lfloor \frac{n}{i} \rfloor$
2.目标值则变为$\sum_{i=1}^{n}i^2 \lfloor \frac{n}{i} \rfloor$
3.由公式$\sum_{i=1}^{n}i^2= \frac{n(n+1)(2n+1)}{6}$ 可以直接计算前缀和部分,对于后者是典型的块状分布,应用数论分块结论$\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$即可。
4.对于溢出数据可以直接用 $int128$ 加快读快写处理,也可以上逆元。
渐近时间复杂度$O(\sqrt{n})$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define int __int128
int n;
inline int read()
{
int res=0,flag=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-') flag=-1;
c=getchar();
}
while(isdigit(c))
{
res=(res<<1)+(res<<3)+(c^48);
c=getchar();
}
return res*flag;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>=10) write(x/10);
putchar('0'+x%10);
}
inline void write(int x,char c)
{
write(x) ;
putchar(c) ;
}
void solve(){
n=read();
int r;
int res=0;
auto sum=[&](int x)->int{
return x*(x+1)*(2*x+1)/6%mod;
};
for(int i=1;i<=n;i=r+1){
int t=n/i;
r=n/t;
res=(res+(sum(r)-sum(i-1))*t%mod)%mod;
}
while(res<0) res+=mod;
write(res);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
// cin>>t;
t=1;
while(t--){
solve();
}
}