数学、数论分块、快速幂、平方和公式
- 很容易超出范围,每一步都要取模
- $g(n) =\sum_ {i=1}^{n} f(i)= \sum_{i=1}^{n} i^2 \times \lfloor \frac{n}{i} \rfloor$
- 分块。按出现次数cnt分块,每块的右边界为$\frac{n}{cnt}$
- 求每块的 $g(j)$ ,用平方和公式 $sum(r)-sum(i-1)$
- 由于每一步都要取模,因此要将平方和公式的除以6变为乘6的乘法逆元
#include <iostream>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
//快速幂 求逆元
ll binpow(ll a,ll b,ll m){
ll res=1;
while(b>0){
if(b&1) res=res*a%m;
a=a*a%m;
b>>=1;
}
return res;
}
//平方和公式 每一步都要取模
ll sum(ll n){
return n*(n+1)%mod *(2*n+1)%mod*binpow(6,mod-2,mod)%mod;
}
int main(){
int n;
scanf("%d",&n);
ll r,res=0;
for(int i=1;i<=n;i=r+1){
int cnt=n/i;
r=n/cnt;
//sum()中存在取模运算,进行取模后sum(r)可能会小于sum(i-1)
//相减后可能为负数,加上模再模
res=((res+cnt*(sum(r)-sum(i-1)))%mod+mod)%mod;
}
printf("%lld",res);
return 0;
}