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

题目描述

给出正整数$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)$种，数论分块即可

代码

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main() {
    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("%lld\n", ans);
}