CQOI 2007 余数之和

题意

求 ${\sum }_{i=1}^{n}k\mathrm{m}\mathrm{o}\mathrm{d}i\backslash sum\_\{i=1\}^n\; k\backslash bmod\; i$，其中 $1\le n,k\le 10^{9}1\backslash le\; n,k\backslash le10^9$。

思路

因为 $k\mathrm{m}\mathrm{o}\mathrm{d}i=k-\lfloor \frac{k}{i}\rfloor \cdot ik\backslash bmod\; i=k-\backslash lfloor\backslash frac\; ki\backslash rfloor\backslash cdot\; i$，所以 ${\sum }_{i=1}^{n}k\mathrm{m}\mathrm{o}\mathrm{d}i={\sum }_{i-1}^{n}k-\lfloor \frac{k}{i}\rfloor \cdot i=nk-{\sum }_{i-1}^n\lfloor \frac{k}{i}\rfloor \cdot i\backslash sum\_\{i=1\}^n\; k\backslash bmod\; i=\backslash sum\_\{i-1\}^n\; k-\backslash lfloor\backslash frac\; ki\backslash rfloor\backslash cdot\; i=nk-\backslash sum\_\{i-1\}^n\backslash lfloor\backslash frac\; ki\backslash rfloor\backslash cdot\; i$。$nknk$ 易求，专门考虑该式后半部分 ${\sum }_{i-1}^n\lfloor \frac{k}{i}\rfloor \cdot i\backslash sum\_\{i-1\}^n\backslash lfloor\backslash frac\; ki\backslash rfloor\; \backslash cdot\; i$。

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

不难发现 $\lfloor \frac{k}{i}\rfloor \backslash lfloor\backslash frac\; ki\backslash rfloor$ 单调不上升，也就是说，$\lfloor \frac{k}{i}\rfloor \backslash lfloor\backslash frac\; ki\backslash rfloor$ 的同一个值一定会连续出现。

不妨设 $\lfloor \frac{k}{i}\rfloor =x\backslash lfloor\backslash frac\; ki\backslash rfloor=x$ 时 $ii$ 的取值范围为 $l_x\le i\le r_{x}l\_x\backslash le\; i\backslash le\; r\_x$，那么应用等差数列求和公式可得 ${\sum }_{i=1}^n\lfloor \frac{k}{i}\rfloor \cdot i=\sum (x{\sum }_{i=l_x}^{r_x}i)=\sum \frac{1}{2}x(l_x+r_x)(r_x-l_x+1)\backslash sum\_\{i=1\}^n\backslash lfloor\backslash frac\; ki\backslash rfloor\backslash cdot\; i=\backslash sum(x\backslash sum\_\{i=l\_x\}^\{r\_x\}i)=\; \backslash sum\backslash frac12x(l\_x+r\_x)(r\_x-l\_x+1)$。

为了计算的方便，枚举 $ll$ 而不是 $xx$。枚举从 $11$ 开始，每算完一段就令 $l=r+1l=r+1$。显然 $x=\lfloor \frac{k}{l}\rfloor x=\backslash lfloor\backslash frac\; kl\backslash rfloor$ ，难点在于求出 $rr$。

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

• 根据我们对右端点 $rr$ 的定义以及数列的单调不升性，$\lfloor \frac{k}{r}\rfloor =x\backslash lfloor\backslash frac\; kr\backslash rfloor=x$ 且 。根据向下取整的定义，$\lfloor a\rfloor \backslash lfloor\; a\backslash rfloor$ 为整数且 。
• 对于 $\lfloor \frac{k}{r}\rfloor =x\backslash lfloor\backslash frac\; kr\backslash rfloor=x$ 这部分，有 $\frac{k}{r}\ge \lfloor \frac{k}{r}\rfloor =x\backslash frac\; kr\backslash ge\backslash lfloor\backslash frac\; kr\backslash rfloor=x$，而 $r,xr,\; x$ 都是正数，则 $\frac{k}{x}\ge r\backslash frac\; kx\backslash ge\; r$。
• 对于 这部分，因为 $\lfloor \frac{k}{r+1}\rfloor \backslash lfloor\backslash frac\{k\}\{r+1\}\backslash rfloor$ 与 $xx$ 都是整数，所以 $\lfloor \frac{k}{r+1}\rfloor +1\le x\backslash lfloor\backslash frac\{k\}\{r+1\}\backslash rfloor+1\backslash le\; x$。又因为 ，所以 。进一步得到 。
• 上述两个结论连起来，得到 。又因为 $rr$ 为整数，所以 $r=\lfloor \frac{k}{x}\rfloor r=\backslash lfloor\backslash frac\; kx\backslash rfloor$。

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

实现

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

注意边界。因为 $\lfloor \frac{k}{x}\rfloor >n\backslash lfloor\backslash frac\; kx\backslash rfloor>n$ 的情况可能存在，需要 r = min(k / x, n); 一下。

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

必须注意 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;
}

写在最后

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

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

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

据说这题的方法有个专门的名字“分块除法”。该算法实际上就是根据整除的结果分成多个部分，每个部分分别计算。最典型的分块除法问题就是本题中 ${\sum }_{i-1}^n\lfloor \frac{k}{i}\rfloor \cdot i\backslash sum\_\{i-1\}^n\backslash lfloor\backslash frac\{k\}\{i\}\backslash rfloor\backslash cdot\; i$。