首页 > 其他 > 详细

BZOJ 1257 余数之和sum(分块优化)

时间:2015-09-09 22:35:10      阅读:332      评论:0      收藏:0      [点我收藏+]

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=46954

题意:f(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n,输入n, k,求f(n, k)。

思路:n>k的部分都为k,直接判断即可。n < k时,k mod n = k - k / n * n,观察发现在一定的区间[lhs, rhs]内k/i的值不变。那么就可以直接分块了,  k/lhs * lhs + k/(lhs+1) * (lhs+1) + ... + k/(rhs+1)*(rhs+1)前一部分是相等的可以一次性处理,最后我们发现,在区间[i, k/(k/i)]这个区间内k/x的值不变。

code:

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long LL;
 5 int main()
 6 {
 7     LL n, k;
 8     while (scanf("%lld %lld", &n, &k) != EOF) {
 9         LL ans = 0;
10         if (n > k) {
11             ans += (n - k) * k;
12             n = k;
13         }
14         ans += n * k;
15         for (LL i = 1, la; i <= n; i = la + 1) {
16             la = min(n, k/(k/i));    // 得到区间上界
17             ans -= (k / i) * (i + la) * (la - i + 1) / 2;
18         }
19         printf("%lld\n", ans);
20     }
21     return 0;
22 }

BZOJ 1257 余数之和sum(分块优化)

原文:http://www.cnblogs.com/ykzou/p/4796096.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!