思路
有难度的一道题
题解是考虑根号分块。那么我们就往这方面想。
首先我们多列几个数字看看吧
这里有一个数学规律,就是因子 $i$ 在 $1\sim n$ 中出现的次数为 $\lfloor \frac{n}{i}\rfloor$,那么其可以对答案做出的贡献就是 $i^2\times \lfloor \frac{n}{i}\rfloor$
可是这样还是需要遍历每一个 $i$,可以过前 30pts 的分。但是其实根号分治已经很明显了。
我们把 $i$ 分成 $≤\sqrt n$ 和 $>\sqrt n$ 两部分,分别称之为 $a,b$
-
对于 $a$,我们可以暴力计算答案。
-
对于 $b$,我们发现会有很多段连续的 $b$ 的取值使得每一段里 $b$ 可以给出的贡献都是相同的。设这一段为 $[l,r]$,那么对于 $b=l,\dots,r$,它们对答案的贡献都是 $\lfloor \frac{n}{l}\rfloor$。那么我们就可以人一个指针 $p$ 从 $\sqrt n+1$ 开始,每一次二分确定 $[p,r]$ 使得对于 $b=p,\dots,r$,它们对答案的贡献都是 $\lfloor \frac{n}{p}\rfloor$,一次性统计 $[p,r]$ 的答案后把指针移动到 $r+1$。
这里还需要一个平方和公式
$\sum\limits_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ps second
#define pf first
#define rd read()
inline int read(){
int xx=0,ff=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') ff=-1;c=getchar();}
while(c>='0'&&c<='9') xx=xx*10+(c-'0'),c=getchar();
return xx*ff;
}
inline void write(int out){
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int M=2e6+5;
const int N=3e5+5;
const int INF=1e9+5;
const int MOD=1e9+7;
int n;
int ans;
int inv[10];
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%MOD;
b>>=1;
a=(a*a)%MOD;
}
return res;
}
int cal(int x){
return x*x%MOD*(n/x)%MOD;
}
void init(){
inv[6]=ksm(6,MOD-2);
// cerr<<inv[6]<<"inv"<<endl;
}
signed main(){
n=rd;
init();
int sq=sqrt(n);
int p=1;
//下面写写锅了,就直接全用第二分块了,复杂度就并列加了O(sqrt(n)log n),不大
// for(p=1;p<=sq;p++){
// ans+=cal(p);
// ans%=MOD;
// }
// cerr<<"ans1="<<ans<<endl;
// p++;
while(1){
int res=n/p;
int l=p,r=n+1;
while(r-l>1){
int mid=l+r>>1;
if(n/mid<res)r=mid;
else l=mid;
}
if(l>n)l=n;
cerr<<p<<' '<<l<<endl;
//最后l是合法的右边界
ans+=((((l*(l+1)%MOD*(2*l+1)%MOD*inv[6])-((p-1)*((p-1)+1)%MOD*(2*(p-1)+1)%MOD*inv[6]))%MOD+MOD)%MOD*(n/p)%MOD)%MOD;
ans=(ans+MOD)%MOD;
p=l+1;
if(p>n)break;
}
cout<<ans%MOD<<endl;
}
大佬6的