_bzoj1257 [CQOI2007]余数之和sum【小技巧】

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1257

最近刚做了一道莫比乌斯的题，需要用到这种方法。

应该让k / i相等的一连串k % i相加，举个例子：

100 / 34 = 2 ... 32

100 / 35 = 2 ... 30

100 / 36 = 2 ... 28

...

100 / 50 = 2 ... 0

可以观察到，商相同的余数数列是公差为商的相反数的等差数列，用求和公式就可以O(1)计算。

那么程序该怎么写呢？注意，如果当前的除数是i，那么[i, n / (n / i)]这个区间所有的数作为除数时，商都相同，那么之后就简单了。

#include <cstdio>

#include <algorithm>

int n, k;

long long ans;

int main(void) {

    scanf("%d%d", &n, &k);

    int last, lmt = std::min(n, k), d;

    long long tem;

    if (n > k) {

        ans = (long long)k * (n - k);

    }

    for (int i = 1; i <= lmt; i = last + 1) {

        d = k / i;

        last = std::min(k / d, lmt);

        tem = last - i + 1;

        ans += tem * (k % i) - ((tem * (tem - 1)) >> 1) * d;

    }

    printf("%lld\n", ans);

    return 0;

}

巴特西

_bzoj1257 [CQOI2007]余数之和sum【小技巧】

最新文章

热门文章