洛谷P2261 余数求和

整除分块的小应用。

考虑到 k % x = k - (k / x) * x

所以把 x = 1...n 加起来就是 k * n - (k / i) * i

i = 1...k(注意这里是k)

对于这个 k / i 就可以整除分块了。

还要注意 k 与 n 的大小关系。

当 k < n 的时候,只需减去不大于k的部分即可。

当 n < k 的时候,注意别让 i > n 就行了。

 #include <cstdio>
#include <algorithm>
typedef long long LL; inline void solve() {
LL n, k;
if(scanf("%lld%lld", &n, &k) == EOF) {
exit();
}
LL ans = n * k;
for(LL i = , j; i <= std::min(k, n); i = j + ) {
j = std::min(k / (k / i), n);
ans -= (k / i) * ((i + j) * (j - i + ) / );
} printf("%lld", ans);
return;
} int main() {
solve();
return ;
}

AC代码

上一篇:fir.im Weekly - 17 个提升 iOS 开发效率的必备工具


下一篇:iOS开发技巧系列---详解KVC(我告诉你KVC的一切)