[CF616E]Sum of Remainders

其实和余数求和是同一道题...
但是范围加大取模就有点容易载坑

还是说一下思路吧

首先我们要求的是:

$$\displaystyle\sum_{i=1}^m n\ mod \ i$$

其实取模操作特殊在没有什么特殊性
基本上看到这种形式就会想到 $n\ mod\ i=n- \left\lfloor\frac{n}{i}\right\rfloor\times i$

于是我们其实就是要求
$$n\times m-\displaystyle\sum_{i=1}^m\left\lfloor\frac{n}{i}\right\rfloor\times i$$

左边这一坨很好求,右边这一坨就要用到整除分块

其实也不是什么难理解的东西,其实就是整除中,被除数一定的情况下,商随除数的增大而减小
由于是整数,所以这个减小是呈现出阶梯状的.
于是我们就想通过当前的商,来推出当前阶梯在截止(在哪里需要减小)

听起来很难,其实稍微理解下就好(以下为非严谨但是易于理解的证明)
首先我们设 $t=\left\lfloor\dfrac{n}{i}\right\rfloor$
这个就是我们当前阶梯的高度了
$t$ 的数学含义是, $n$ 里面包含了几个 $i$
假设我们现在每个阶梯高度都是 $t$
那么最多能维持多少个阶梯呢
答案显然是 $\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$ 个
于是我们的右边界就算出来了(还要对边界取min),时间复杂度$O(\sqrt{N})$

好吧我承认这样可能更难理解orz

好吧 我就给出严谨一点的证明
对于 $x\in [1,n]$ , 设 $g(x)=\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor$
设 $f(x)=\dfrac{n}{x}$ 注意这里的 $n$ 为常数
对 $f(x)$ 求导得到 $f'(x)=-\dfrac{n}{x^2}$ 在 $[1,n]$ 衡小于0
$f(x)$ 在 $[1,n]$ 单调递减
而 $g(x)\ge \left\lfloor\dfrac{n}{\frac{n}{x}}\right\rfloor=x$
所以 $\left\lfloor\dfrac{n}{x}\right\rfloor\ge \left\lfloor\dfrac{n}{g(x)}\right\rfloor$

而且, $\left\lfloor\dfrac{n}{g(x)}\right\rfloor\ge \left\lfloor\dfrac{n}{\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}}\right\rfloor=\left\lfloor\dfrac{n}{x}\right\rfloor$

所以 $\left\lfloor\dfrac{n}{x}\right\rfloor=\left\lfloor\dfrac{n}{g(x)}\right\rfloor$

这个 $x$ 就是我们刚刚枚举的 $i$
可以注意到,我们求出了一个 $g(x)$ 肯定是不小于 $x$ 但是它们的整除 $n$ 的值却是一样的,且它是符合要求的数里面最大的.

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注