如果你觉得 \(O(n)\) 没有跑到极限的话,你可以试试整除分块。
先来化一下式子:
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\;[i\bmod j\ge k]
\]
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\;[i-\left\lfloor\dfrac{i}{j}\right\rfloor\times j\ge k]
\]
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\;[\left\lfloor\dfrac{i}{j}\right\rfloor\times j\le i-k]
\]
这个 \(\left\lfloor\frac{i}{j}\right\rfloor\) 长得就很能整除分块。然后就是基础的操作了,我们枚举 \(i\),对于每个 \(j\),一直到 \(\left\lfloor\frac{i}{\left\lfloor\frac{i}{j}\right\rfloor}\right\rfloor\),\(\left\lfloor\frac{i}{j}\right\rfloor\) 的取值都不变,但是这里还有一个 \(\times j\) 没有处理。我们可以把 \(\left\lfloor\frac{i}{j}\right\rfloor\) 除过去,算一下 \(\left\lfloor\frac{i-k}{\left\lfloor\frac{i}{j}\right\rfloor}\right\rfloor\),也就是最大可以乘多大的 \(j\),再与当前块的左端点作比较即可。需要注意 \(\left\lfloor\frac{i}{j}\right\rfloor=0\) 的情况,特殊处理。
时间复杂度 \(O(n\sqrt n)\)。
code:
int main()
{
n=read(),k=read();
ll ans=0;
FOR(i,1,n){
for(int l=1,r;l<=n;l=r+1){
if(i/l==0) r=n;
else r=min(i/(i/l),n);
int t=i/l;
if(t==0){
if(i-k>=0) ans+=r-l+1;
continue;
}
t=(i-k)/t;
ans+=max(0,t-l+1);
}
}
printf("%lld\n",ans);
return 0;
}