# 整除分块
与其说整除分块是一种算法,不如说它是一个技巧。有时我们需要计算这样的式子:
根据经验,我们发现 只有 种取值。对于每种取值, 都会有一个连续的范围。假设函数 的前缀和可以预处理后快速求出,那么我们可以枚举 的所有取值,并和 的连续一段的和相乘。具体可以见代码:
//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 小凯的数字
我们知道,一个数模 等于他的各位和模 。这一结论可以推广至将某数截成若干节,每段合起来也符合这个规律,题目便转化成求 。用 __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; | |
} |