数论：整除问题

整除分块

与其说整除分块是一种算法，不如说它是一个技巧。有时我们需要计算这样的式子：

$$
\sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor
$$

根据经验，我们发现 $\lfloor\frac{n}{i}\rfloor$ 只有 $O(\sqrt n)$ 种取值。对于每种取值，$i$ 都会有一个连续的范围。假设函数 $f$ 的前缀和可以预处理后快速求出，那么我们可以枚举 $\lfloor\frac{n}{i}\rfloor$ 的所有取值，并和 $f$ 的连续一段的和相乘。具体可以见代码：

// s[i] 为函数 f(i) 的前缀和 
int ans = 0;
for(int i=1, j; i<=n; i=j+1) {
    j = n/(n/i);
    ans += (s[j]-s[i-1])*(n/i);
}
printf("%d\n", ans);

杂题

P4942 小凯的数字

我们知道，一个数模 $9$ 等于他的各位和模 $9$。这一结论可以推广至将某数截成若干节，每段合起来也符合这个规律，题目便转化成求 $\sum_{i=l}^{r} i\pmod 9$。用 __int128 也可以过，但是更好是把除以二挪到前面，使其符合乘法取模分配率，注意奇偶。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long LL;

int a[15], b[15];

int main() {
    int q; scanf("%d", &q);
    for(int i=1; i<=q; ++i) { LL l, r;
        scanf("%lld%lld", &l, &r);
        if((r-l+1) %2 == 0) printf("%lld\n", ((r-l+1)/2)%9*(l+r)%9);
        else printf("%lld\n", ((l+r)/2)%9*(r-l+1)%9);
    }
    return 0;
}