Tony102's Blog - 整除分块
type: channel
link: https://tony102.com/index.php/tag/%E6%95%B4%E9%99%A4%E5%88%86%E5%9D%97/
items: CF616E Sum of Remainders

CF616E Sum of Remainders
type: item
date: 2020-11-14T14:11:00+08:00
description: linkSol现在让你求的是$$ \sum_{i = 1}^{m} n \ mod \ i $$模运算这种东西就是带余除法，然后你发现余数你也很不好算。就考虑把模运算改成带余除法的形式我们知道: $x \div i = \lfloor \frac{x}{i} \rfloor + x - (i \times \lfloor \frac{x}{i} \rfloor)$所以现在要求的东西就是$$ \sum_{i=1}^{m} n - (i \times \lfloor \frac{n}{i} \rfloor) $$$$ n \times m - \sum_{i=1}^{m} i \times \lfloor \frac{n}{i} \rfloor $$所以后面的东西整除分块一下就好了Code#include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; int n, m; namespace ae86 { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (!isdigit(c))b ^= c == '-', c = fetch(); while (isdigit(c)) a = a * 10 + c - 48, c = fetch(); return b ? a : -a; } } using ae86::read; inline int qPow(int a, int b) { int ans = 1; while (b) { if (b & 1) ans = ans * a % mod; b >>= 1, a = a * a % mod; } return ans % mod; } inline int minux(int a, int b) { return (a - b + 10 * mod) % mod; } signed main() { // freopen("code.in", "r", stdin); // freopen("code.out", "w", stdout); n = read(), m = read(); int ans = (n % mod) * (m % mod) % mod, mul = qPow(2, mod - 2); for (int l = 1, r = 0; l <= m; l = r + 1) { if (n / l == 0) r = m; else r = std::min(m, (n / (n / l))); ans = (ans - 1ll * (n / l) % mod * ((l + r) % mod) % mod * ((r - l + 1ll) % mod) % mod * mul % mod + 10ll * mod) % mod; } printf("%lld\n", ans % mod); return 0; }