CF616E Sum of Remainders 题解

· · 题解

分析

整除分块板子题（几乎与 P2261 完全相同）

首先，我们来推一波式子

\begin{aligned} \sum \limits_{i = 1}^m n \bmod i &= \sum \limits_{i = 1}^m(n - \lfloor\dfrac n i \rfloor i)\\ &= nm - \sum \limits_{i = 1}^m\lfloor\dfrac n i \rfloor i\\ \end{aligned}

我们发现，\sum \limits_{i = 1}^m\lfloor\dfrac n i \rfloor i 可以通过枚举不同的 \lfloor\dfrac n i \rfloor 处理，而这个枚举可以通过整除分块来实现。

不难发现不同的 \lfloor\dfrac n i \rfloor 仅有 O(\sqrt n) 个，通过整除分块枚举一遍是 O(\sqrt n) 复杂度

代码

#include <stdio.h>
template<class T>
inline T min(const T &x, const T &y) { return x < y ? x : y; }
template<class T>
inline T max(const T &x, const T &y) { return x < y ? y : x; }
#define lld long long
const lld mod = 1e9 + 7;
lld n, m;
lld l, r;
lld ans;
int main() {
    scanf("%lld%lld", &m, &n);
    ans = (n % mod) * (m % mod);
    lld inv2 = (mod + 1) >> 1;
    for (l = 1; l <= n && l <= m; l = r + 1) {
        r = min(m / (m / l), n);
        ans = (ans - (m / l) % mod * ((l + r) % mod) % mod * ((r - l + 1) % mod) % mod * inv2 % mod) % mod; // 记得取模
    } // 整除分块
    printf("%lld\n", (ans + mod) % mod);
}