# 整除分块

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

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

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

//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 小凯的数字

我们知道,一个数模 99 等于他的各位和模 99。这一结论可以推广至将某数截成若干节,每段合起来也符合这个规律,题目便转化成求 i=lri(mod9)\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;
}
更新于