这道题目这么算:
化简到$(11)$时可以先像下表一样列一个式$(12)$的表。
根据$\lfloor \frac ki\rfloor$的值将$(12)$分成若干段来求和,每段都是一个等差数列。其中段数是$\sqrt n$级别的。可以根据$(14)\sim(16)$的信息来通过一段的信息来求下一段的信息。
倘若$n>k$,则$k+1\sim n$地方的值都是$k$,提前算好。
本题用到了数论分块的思想,这会在多处别的地方用到。
code:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n=15,k=20,ans=0,s;
cin>>n>>k;
s=n;
if(n>k)n=k;
for(long long d=k,l=1,r=1;;l=r+1,d=k/l,r=k/d){
r=min(r,n);
ans+=d*(l+r)*(r-l+1)/2;
if(r==n)break;
}
cout<<s*k-ans;
return 0;
}