AcWing - 199 - 余数之和 = 数论分块

https://www.acwing.com/problem/content/201/

要注意这次的数论分块里面是有一个上界n的，对k进行分块的时候l和r都不能超过n。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll s1(ll n) {
    return n * (n + 1) / 2;
}

ll calc(ll n, ll k) {
    ll ans = n * k;
    //cout<<"ans="<<ans<<endl;
    ll res = 0;
    ll N = min(n, k);
    for(ll l = 1, r; l <= N; l = r + 1) {
        r = min(N, k / (k / l));
        //printf("[%lld,%lld]\n",l,r);
        res += (s1(r) - s1(l - 1)) * (k / l);
    }
    return ans - res;
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int n, k;
    while(~scanf("%d%d", &n, &k)) {
        printf("%lld\n", calc(n, k));
    }

    return 0;
}

AcWing - 199 - 余数之和 = 数论分块

原文：https://www.cnblogs.com/Inko/p/11468633.html