\(Decription:\)

给出两个数n,k,求\(\sum_{i=1}^{n}k\%i\)

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

\(Sample\) \(Input:\)

10 5

\(Sample\) \(Output:\)

29

这题要求余数的和,考虑和除法有些密不可分的关系,那就化化式子

\(\sum_{i=1}^{k} k-k/i*i\)

\(n*k-\sum_{i=1}^{k} k/i*i\)

那么我们考虑用除法分块求。

每一个块内的和是等差数列,那么可以快速就出一个块的和。

因为块的个数不会对于根号个,所以复杂度有保证。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,ans,l,r;
signed main(){
    scanf("%lld%lld",&n,&k);
    for(l=1;l<=n;l=r+1){
        if(k/l!=0) r=min(k/(k/l),n);
        else r=n;
        ans-=(k/l)*(r-l+1)*(l+r)>>1;
    }
    ans+=n*k;
    printf("%lld\n",ans);
    return 0;
}
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄