Bzoj 1257 [CQOI2007]余数之和 (整除分块)

Bzoj 1257 [CQOI2007]余数之和 (整除分块)

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1257
一道简单题.
题目要求:

[sum_{i=1}^nx \% i = ]

[sum_{i=1}^nk - i * [dfrac{k}{i}] = ]

[n * k - sum_{i=1}^n i * [dfrac{k}{i}] ]

后面这一部分可以用整除分块解决.
需要注意的是.(k\%i(i > k)) 时,运用整除分块,程序会出错,因为除了(0),显然(i>k)时,不会对答案造成影响.整除分块的时候只需要枚举到(min(n,k))即可.
还需要一点等差数列的知识.
(l+(l+1)+(l+2)+(l+3)..r)
这一部分的和就是((l + r) /2 * (r - l + 1))区间的平均值乘以区间元素个数.
然后就做完了.
时间复杂度:(O(sqrt n))
CODE

#include <iostream>
#include <cstdio>
#define ll long long

ll ans,n,k;

ll min(ll a,ll b) {return a > b ? b : a;}
ll max(ll a,ll b) {return a > b ? a : b;}

int main() {
    scanf("%lld%lld",&n,&k);
    ans = n * k;
    for(ll l = 1,r;l <= min(k,n);l = r + 1) {
        r = min( k / (k / l) , n );
        ans -= (k / l) * (r - l + 1) * (r + l) / 2;
    }
    printf("%lld",ans);
    return 0;
}