首页 > 其他 > 详细

洛谷P2261 [CQOI2007]余数求和

时间:2019-10-26 10:01:41      阅读:86      评论:0      收藏:0      [点我收藏+]

题目

数论,考虑原题给的公式,得出\(i\%j=i-(i/j)*j)\)

原题求\(\sum_{i=1}^{i=n}(k\%i)=\sum_{i=1}^{i=n}(k-i*(k/i))=k*n-\sum_{i=1}^{i=n}(i*(k/i))\)

因此原题转化成了快速求\(\sum_{i=1}^{i=n}(i*(k/i))\)\(k/i\)在一段时间内是不变的,因此考虑数论分块。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, ans;
signed main()
{
    scanf("%lld%lld", &n, &k);
    ans = n * k;
    int l, r;
    for (l = 1, r; l <= n; l = r + 1)//l即i,r是满足k/l与k/r相等的数的最右边一位,易得k/(k/l)和n的最小值即为r,然后再用l,r的区间长度乘公差为1的等差数列的和,这样的时间复杂度是O(sqrt(n))的
    {
        if (k / l == 0) r = n;
        else r = min(n, k / (k / l));
        ans -= (k / l) * (r - l + 1) * (l + r) / 2 ;
    }
    printf("%lld", ans);
    return 0;
}

洛谷P2261 [CQOI2007]余数求和

原文:https://www.cnblogs.com/liuwenyao/p/11741726.html

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