有难度的
算法1
(数论分块)
首先让我们把所有f(i)加在一起是什么东西
可以发现,统计每种因数的平方的出现次数,
乘以这个因数的平方加和为答案
那么该因数出现了几次呢?显然是所有他的倍数,
有$\lfloor{n/i}\rfloor$次
所以答案为$\sum_{1<=i<=n}{i^2 \lfloor{n/i}\rfloor}$
如何快速计算?
由于n/i至多有2sqrt(n)种取值(当i<=sqrt(n)时有sqrt(n)种,i>sqrt(n)时 n/i<sqrt(n)所以也有sqrt(n)种)所以对于每种n/i可以
一次性计算。
性质:
$max(i:(n/i)=(n/j))=(n/(n/j))$
证明:
$\because (n/i)<=\frac{n}{i}$
$\therefore \frac{(n/i)}{n}<=\frac{1}{i}$
$\therefore \frac{n}{(n/i)}>={i}$
$\therefore i_{max}=n/(n/i)$
$\square$
时间复杂度
$O(\sqrt n)$
C++ 代码
#include<bits/stdc++.h>
const int N = 1e6 + 33,inf=2e9,mod=1e9+7;
int n;
int ans=0;
int qpow(int b,int e){
int ret=1;
while(e){
if(e&1)ret=(ll)ret*b%mod;
e>>=1;
b=(ll)b*b%mod;
}
return ret;
}
#define xx(x) (x=(x%mod+mod)%mod)
int calc(int n){
int ans=0;
fr(x,1,n){
ans=(((ll)n/x)*x*x+ans)%mod;
}
return ans;
}
int CNT=0;
int main() {
rd(n);
int i;
for(i=1;i<=n;){
int q=(n/i);
int l=(n/(q+1))+1;
int r=(n/q);
assert(l<=r);
CNT+=r-l+1;
auto f=[](int p){return (ll)p*(p+1)%mod*(2*p+1)%mod*qpow(6,mod-2)%mod;};
ans=(((ll)q*(f(r)-f(l-1)))+ans)%mod;
xx(ans);
i=r+1;
}
pt("%d\n",ans);
return 0;
}