都不知道说什么好。。。咕咕到现在。。
求:$\sum_{i=1}^n \space k\space mod \space i$
即求:$n*k-\sum_{i=1}^n\space \lfloor \frac{k}{i} \rfloor *i$
我们发现,在一定范围内,$\lfloor \frac{k}{i} \rfloor$是不变的,那么此时相当于求一个等差数列。。。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define R register ll
static char B[<<],*S=B,*D=B;
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
using namespace std;
inline ll g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
} ll n,k,ans;
signed main() {
n=g(),k=g(); ans=n*k; for(R l=,r=;l<=n;l=r+) {
if(k/l) r=min(n,k/(k/l));//求出左右边界
else r=n;
ans-=(k/l)*(r-l+)*(l+r)>>;
} printf("%lld\n",ans);
}
2019.06.04