[Luogu 2261] CQOI2007 余数求和

[Luogu 2261] 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 \neq 0\),则 \(r = \min (\lfloor \frac{k}{t} \rfloor , n)\);

  • \(t = 0\),则 \(r = n\)。

(请自行打草稿验证。)

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

每一块的和 \(=\) 当前块的 \(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;
}

谢谢阅读。

上一篇:(1)ActivityThread分析


下一篇:IntelliJ IDEA安装bower