首页 > itarticle > 莫比乌斯反演习题：bzoj 1257 [cqoi2007]余数之和

莫比乌斯反演习题：bzoj 1257 [cqoi2007]余数之和

admin 11月 13, 2020 0

题目描述

给出正整数$n$和$k$，计算$f(n, k)=k text{ mod } 1 + k text{ mod } 2 + k text{ mod } 3 + cdots + k text{ mod } n$的值

其中$k text{ mod } i$表示$k$除以$i$的余数

$n,k le 10^9$

题解

$$
begin{aligned}
f(n,k)
&=sum_{i=1}^{n}k text{ mod }i \
&=sum_{i=1}^{n}k - lfloor frac{k}{i} rfloor i \
&=nk - sum_{i=1}^{n} i lfloor frac{k}{i} rfloor \
end{aligned}
$$

显然$lfloor frac{k}{i} rfloor$的取值只有$O(sqrt k)$种，数论分块即可

代码


using namespace std;
typedef long long ll;

int () {
    int n, k; scanf("%d%d", &n, &k);
    ll ans = (ll) n * k;
    for(int i = 1, j ; i <= n && k / i != 0 ; i = j + 1)
        j = min(n, k / (k / i)),
        ans -= (ll) (i + j) * (j - i + 1) / 2 * (k / i);
    printf("%lldn", ans);
}