CF616E Sum of Remainders

2020 年 11 月 14 日

1519 次浏览

927字数

<div class="list-group list-group-lg list-group-sp row" style="margin: 0"></div>(https://www.luogu.com.cn/problem/CF616E)

## Sol

现在让你求的是

$$
\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

```cpp
#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;
}
```

最后修改：2021 年 09 月 04 日