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

洛谷传送门

题解

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

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

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

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

$$ans=\sum _n^{i=1}k\mathrm{mod}i$$

$$=\sum _n^{i=1}k-i\times \lfloor \frac{k}{i}\rfloor$$

这样的话，直接用数论分块就可以解决：先使同一块的 $\frac{k}{i}$ 相等，那么剩下的就是一个等差数列求和。时间复杂度 $O(\sqrt{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;
}