Luogu P2261 余数求和(除法分块)
文章目录
题目描述
给定正整数$n$和$k$
求 $ans = \sum_{i = 1}^n k \bmod i$
要求 $\mathcal{O}(\sqrt{k})$ 时间复杂度
简要做法
$$ans = \sum_{i = 1}^n k \bmod i$$
$$ans = \sum_{i = 1}^n(k- i \times {\lfloor\frac{k}{i}\rfloor})$$
$$ans = n \times k - \sum_{i = 1}^n (i \times \lfloor\frac{k}{i}\rfloor)$$
但似乎到这里我们就不会做了
但是经验告诉我们
数论先打表
于是将$\lfloor\frac{k}{i}\rfloor$打表
当$n = 10 , k = 5$时
$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$被分成了连续的几块
于是便可以用 $n \times k$ 减去每一块的和求出答案
设$l$代表当前块的左端点
设$r$代表当前块的右端点
此时枚举$l$
即可通过 $l$ 和 $k$ 求出 $r$
设$t = \lfloor\frac{k}{i}\rfloor$
-
若$t \ne 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 $ 继续处理下一块即可
复杂度分析
对于 $\lfloor\frac{k}{i}\rfloor$
- 若 $i \le \sqrt k$ 最多只有 $ \sqrt k $ 种取值
- 若 $i > \sqrt k$ 则 $\lfloor\frac{k}{i}\rfloor < \sqrt k$ 取值也不超过 $\sqrt k$ 种
故 $\lfloor\frac{k}{i}\rfloor$ 最多只有 $2 \times \sqrt k$ 种取值
所以整除分块的时间复杂度为$\mathcal{O}(\sqrt{k})$
参考代码
#include <stdio.h>
#include <algorithm>
long long n, k, ans;
int main()
{
scanf("%lld%lld", &n, &k);
ans = n * k;
for (long long l = 1, r; l <= n; l = r + 1)
{
long long t = k / l;
if (t == 0)
r = n;
else
r = std::min(k / t, n);
ans -= t * (r - l + 1) * (l + r) / 2;
}
printf("%lld", ans);
return 0;
}