题解 P2261 【[CQOI2007]余数求和】

· · 题解

这道蓝题是真的简短精炼

下面介绍一个方法：数论（整除）分块

对于单一的⌊n/i⌋，某些地方的值是相同的，并且呈块状分布

通过进一步的探求规律与推理以及打表与瞎猜，我们可以惊喜的发现一个规律，这些块状分布的值是有规律的

对于一个块，假设它的起始位置的下标为l，那么可以得到的是，它的结束位置的下标为⌊n/⌊n/l⌋⌋

这道题在更新r的只是有一个细节要注意：r<=n

调到心态崩溃才发现。。。

推荐blog:数论分块 有个小错误

代码：

#include<bits/stdc++.h>
#define fir(a, b, c) for(register ll a = b; a <= c; a ++)
#define ll long long
using namespace std;

ll n, k;

int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld %lld", &n, &k);
    ll ans = n*k;
    for(ll l = 1ll, r = 0; l <= n; l = r + 1ll){
        if(k/l == 0ll) r = n;
        else r = min(k / (k / l), n);//这个min很重要
        ans -= ((l+r)*(r-l+1ll)/2ll) * (k/l);
    }
    printf("%lld\n", ans);
    return 0;
}