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

· · 题解

这一定是我迄今为止见过最短小精悍的省选题了，核心代码 4 行，总代码 12 行，堪比小凯的疑惑啊。

这题一看暴力很好打，然而 10^{9} 的范围注定会卡掉暴力。

所以我们要用除法分块来优化。

由题意得：ans = \sum_{i=1}^{n} k \bmod i

我们知道，a \bmod b = a - b \times \lfloor \frac{a}{b} \rfloor

因此，ans = \sum_{i=1}^{n} k - i \times \lfloor \frac{k}{i} \rfloor = nk - \sum_{i=1}^{n} i \times \lfloor \frac{k}{i} \rfloor

我们用样例来打表找规律，发现 \lfloor \frac{k}{i} \rfloor 分别在一定的区域内相等，如下表所示：

i 1 2 3 4 5 6 7 8 9 10
\lfloor \frac{k}{i} \rfloor 5 2 1 1 1 0 0 0 0 0

可见 \lfloor \frac{k}{i} \rfloor 分成了 3 块，我们只需要计算 n \times k 减去每一块的和即可。

首先枚举块的左边界 l，并根据左边界和 k 计算出右边界 r。

令 t = \lfloor \frac{k}{l} \rfloor，分两种情况讨论：

（请自行打草稿验证。）

右边界有了，每一块的和也就可以计算出了。

每一块的和 = 当前块的 t \times 当前块元素个数 \times 当前块 i 的平均值 = t \times (r-l+1) \times (l+r) \div 2

当前块处理完后，令 l = r + 1，开始计算下一块，直到计算至 n。

除法分块就是这样，在莫比乌斯反演优化中也有作用的。

给出最短小精悍的省选题代码。

记得开long long！

#include <algorithm>
#include <cstdio>
using std::min;
long long n,k,ans;
int main(int argc,char *argv[])
{
    scanf("%lld %lld",&n,&k);
    for(long long l=1,r,t;l<=n;l=r+1)
        r=(t=k/l) ? min(k/t,n) : n,ans-=t*(r-l+1)*(l+r)>>1;
    printf("%lld\n",ans+n*k);
    return 0;
}

谢谢阅读。

顺便打一波广告qwq