洛谷2261 [CQOI2007]余数求和

Luogu

算法

数论分块。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;
mainint main() {
    int n,k; cin>>n>>k;
    int ans=n*k;
    for (re int l=1,r;l<=n;l=r+1) {
        if (k/l) r=min(k/(k/l),n);
        else r=n;
        ans-=(k/l)*(r-l+1)*(l+r)/2;
    }
    cout<<ans<<endl;
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 27 PM

4 条评论

  1. ych jr

    为什么我做这道题sb到用二分,,,

    1. wsm000
      @ych jr

      像我这样真正的sb只能想到暴力,逃(´இ皿இ`)

      1. M_sea
        @wsm000

        数论分块挺简单的呀qwq

        1. wsm000
          @M_sea

          数论分块和分块关系实在是太小了,容易想偏qwq

发表评论