[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 的值却是一样的,且它是符合要求的数里面最大的.

发表评论

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