CQOI 2007 余数之和

题意

求，其中。

思路

因为，所以。易求，专门考虑该式后半部分。

以下过程与《算法竞赛进阶指南》有差别。

不难发现单调不上升，也就是说，的同一个值一定会连续出现。

不妨设时的取值范围为，那么应用等差数列求和公式可得。

为了计算的方便，枚举而不是。枚举从开始，每算完一段就令。显然，难点在于求出。

关于的取值，下面给出较清晰的推导，方便理解。

根据我们对右端点的定义以及数列的单调不升性，且。根据向下取整的定义，为整数且。
对于这部分，有，而都是正数，则。
对于这部分，因为与都是整数，所以。又因为，所以。进一步得到。
上述两个结论连起来，得到。又因为为整数，所以。

最后发现，此处得到的结论与书中结论相同。

实现

NowCoder 4ms。Luogu 40ms，单点3~5ms。（似乎两个网站用时计算方法不一样。）

注意边界。因为的情况可能存在，需要 r = min(k / x, n); 一下。

代码中另外有一点解释一下。我在 for 循环的判断条件中，加入书中没有的 l <= k。这是因为当时，显然等于，没有必要再算了。

必须注意 long long 的问题，l, r, x 不开 long long 会WA。

#include <cstdio>
#include <algorithm>

using namespace std;

long long n, k, ans;

int main() {
    scanf("%lld%lld", &n, &k);
    ans = n * k;
    long long l, r, x;
    for (l = 1; l <= n && l <= k; l = r + 1) {
        x = k / l;
        r = min(k / x, n);
        ans -= x * (l + r) * (r - l + 1) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

写在最后

虽然基于教材做例题，但是推导还是必须自己推导的。

似乎自己这样的推导在思路上比较容易想到。当然在做题过程中还是要用之类的小数据试一下的。

写题解时书不在身边，印象中书中只说明了从到除法取整的结果相同，但是没有说明和结果不同。

据说这题的方法有个专门的名字“分块除法”。该算法实际上就是根据整除的结果分成多个部分，每个部分分别计算。最典型的分块除法问题就是本题中。