首页 > 代码库 > _bzoj1257 [CQOI2007]余数之和sum【小技巧】
_bzoj1257 [CQOI2007]余数之和sum【小技巧】
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1257
最近刚做了一道莫比乌斯的题，需要用到这种方法。
应该让k / i相等的一连串k % i相加，举个例子：
100 / 34 = 2 ... 32
100 / 35 = 2 ... 30
100 / 36 = 2 ... 28
...
100 / 50 = 2 ... 0
可以观察到，商相同的余数数列是公差为商的相反数的等差数列，用求和公式就可以O(1)计算。
那么程序该怎么写呢？注意，如果当前的除数是i，那么[i, n / (n / i)]这个区间所有的数作为除数时，商都相同，那么之后就简单了。
#include <cstdio>
#include <algorithm>
int n, k;
long long ans;
int main(void) {
scanf("%d%d", &n, &k);
int last, lmt = std::min(n, k), d;
long long tem;
if (n > k) {
ans = (long long)k * (n - k);
}
for (int i = 1; i <= lmt; i = last + 1) {
d = k / i;
last = std::min(k / d, lmt);
tem = last - i + 1;
ans += tem * (k % i) - ((tem * (tem - 1)) >> 1) * d;
}
printf("%lld\n", ans);
return 0;
}
_bzoj1257 [CQOI2007]余数之和sum【小技巧】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。