【洛谷】P2261 [CQOI2007] 余数求和 的题解

【洛谷】P2261 [CQOI2007] 余数求和 的题解

洛谷传送门

题解

这还是蓝题，这还是省选qaq

题目看着很简单，但是真的很考验思路，思路对了，代码不到 5 5 5 分钟写完。

刚开始做的时候还是一如既往，打了个暴力，成功获得了 40 40 40 的好成绩，T 了一堆，然后开始认真考虑数学做法。

刚开始还是打了个表，发现了对于每个 [ k n + 1 + 1 ， n k ] [\frac{k}{n + 1}+1，\frac{n}{k}] [n+1k​+1，kn​] 的区间，它们的公差都是 n n n。然后继续推算发现

a n s = ∑ n i = 1 k m o d    i ans = \sum_{n}^{i = 1} k \mod i ans=n∑i=1​kmodi

= ∑ n i = 1 k − i × ⌊ k i ⌋ = \sum_{n}^{i = 1} k - i \times \lfloor \frac{k}{i} \rfloor =n∑i=1​k−i×⌊ik​⌋

这样的话，直接用数论分块就可以解决：先使同一块的 k i \frac{k}{i} ik​ 相等，那么剩下的就是一个等差数列求和。时间复杂度 O ( n ) O(\sqrt{n}) O(n ​)。

十年 OI 一场空，不开 long long 见祖宗！！！

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {
	inline int read() {
		register int x = 0, f = 1;
		register char c = getchar();
		while (c < '0' || c > '9') {
			if(c == '-') f = -1;
			c = getchar();
		}
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
	inline void write(int x) {
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
		return;
	}
}
using namespace fastIO;
ll n, k;
int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
    ll ans = n * k;
    for(ll l = 1, r; l <= n; l = r + 1) {
        if(k / l != 0) {
        	r = min(k / (k / l), n); 
		}
        else {
        	r = n;
		}
        ans -= (k / l) * (r - l + 1) * (l + r) / 2;
    }
    cout << ans << endl;
	return 0;
}