数论：整除问题 - 算法 - 数论 | 小林书架

# 整除分块

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

$\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;
	}