积性函数的各种处理(等待重构!)
1:整除
1.1:整除的性质 1
对于 \forall a, b, c \in \mathbb{Z},有:
证明
设 \frac{a}{b} = \left\lfloor \frac{a}{b} \right\rfloor + r,其中 0 \leq r < 1,则:
Q.E.D
1.2:整除的性质 2
给出一个正整数 n,对于正整数 d(1 \leq d \leq n),\left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 2\sqrt{n} 种。
证明
可以分类讨论:
- 若 d \leq \sqrt{n},因为 d 的取值不超过 \sqrt{n} 种,显然 \left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 \sqrt{n} 种。
- 若 d > \sqrt{n},则 \left\lfloor \frac{n}{d} \right\rfloor \leq \sqrt{n},故 \left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 \sqrt{n} 种。
综上所述,\left\lfloor \frac{n}{d} \right\rfloor 的取值不超过 2\sqrt{n} 种,Q.E.D
1.3:整除分块
给出一个正整数 n,请你求出:
其中 1 \leq n \leq 10^9。
分析
观察到函数 f(x) = \frac{n}{x} 在区间 (0, +\infty) 上单调递减。
所以,对于函数 g(x) = \left\lfloor \frac{n}{x} \right\rfloor 的任意一个函数值,令 g(x) 取到该值的所有自变量 x 组成一段连续的区间。
根据「1.2:引理 2」,我们知道这样的区间个数也是 \mathcal{O}(\sqrt{n}) 级别的。
对于一段满足 g(x) 均相等的区间,我们可以直接得出该区间里的所有 x 对答案的贡献。那现在的关键在于如何得到这些区间。
考虑任意一个 i(1 \leq i \leq n),我们现在要找到一个最大的 j(i \leq j \leq n),使得 \left\lfloor \frac{n}{i} \right\rfloor = \left\lfloor \frac{n}{j} \right\rfloor。结论:j = \left\lfloor \frac{n}{ \left\lfloor \frac{n}{i} \right\rfloor } \right\rfloor。
证明
- 第一步,证明其合法性(i \leq j \leq n)。
- 第二步,证明其为最大值。
考虑任意一个满足 \left\lfloor \frac{n}{i} \right\rfloor = \left\lfloor \frac{n}{j} \right\rfloor 的 j:
因为 j \in \mathbb{Z},故 j_{\max} = \left\lfloor \frac{n}{ \left\lfloor \frac{n}{i} \right\rfloor } \right\rfloor。
Q.E.D
实现
根据上述结论,我们就有了找出这 \mathcal{O}(\sqrt{n}) 个区间的方法。直接套结论做即可,时间复杂度是 \mathcal{O(\sqrt{n})} 的。
for (int x = 1, nx; x <= n; x = nx + 1) {
nx = n / (n / x);
ans += 1ll * (nx - x + 1) * (n / x);
}1.4:多维整除分块
给出两个正整数 n, m,请你求出:
其中 1 \leq n, m \leq 10^9。
分析
上式的乘积项包含两个取整分式。
考虑任意一个 i,我们现在要找到一个最大的 j,使得 \left\lfloor \frac{n}{i} \right\rfloor = \left\lfloor \frac{n}{j} \right\rfloor 且 \left\lfloor \frac{m}{i} \right\rfloor = \left\lfloor \frac{m}{j} \right\rfloor。易证:j = \min\left\{\left\lfloor \frac{n}{ \left\lfloor \frac{n}{i} \right\rfloor } \right\rfloor, \left\lfloor \frac{m}{ \left\lfloor \frac{m}{i} \right\rfloor } \right\rfloor\right\}。
扩展到多维也是一样的道理。
2:积性函数
2.1:积性函数的定义
若数论函数 f(n) 满足:对于任意互质正整数 x, y,都有 f(xy) = f(x)f(y)。则 f(n) 为积性函数。
若数论函数 f(n) 满足:对于任意正整数 x, y,都有 f(xy) = f(x)f(y)。则 f(n) 为完全积性函数。
2.2:积性函数的简单性质
- 对于任意积性函数 f(x),都有 f(1) = 1。
- 对于任意积性函数 f(x), g(x),则以下的 h(x) 也均为积性函数:
- 将 x 分解质因数,若 f(x) 为积性函数,则 f(x) = \prod\limits_{i = 1}^m f(p_i^{c_i})。
2.3:常见积性函数
- 单位函数(完全积性):
- 恒等函数(完全积性):
- 常数函数(完全积性):
- 约数函数(积性):
- 欧拉函数(积性):
- 莫比乌斯函数(积性):
3:Dirichlet 卷积
3.1:Dirichlet 卷积的定义
定义两个数论函数 f, g 的 Dirichlet 卷积为:
3.2:Dirichlet 卷积的性质
- 交换律:f \ast g = g \ast f。
- 结合律:(f \ast g) \ast h = f \ast (g \ast h)。
- 分配律:f \ast (g + h) = f \ast g + f \ast h。
- 单位元:f \ast \epsilon = f,因此 \epsilon 也被叫做 Dirichlet 卷积单位元。
3.3:常见 Dirichlet 卷积式
3.3.1:式 1
证明
不难看出关于 n 的函数 f(n) = \sum\limits_{d \mid n} \mu(d) 是个积性函数。
-
当 n = 1 时,显然有 f(1) = 1。
-
当 n > 1 时,将 n 质因数分解,得:
综上所述,f(n) = \sum\limits_{d | n} \mu(d) = [n = 1],Q.E.D
3.3.2:式 2
证明
不难看出关于 n 的函数 f(n) = \sum\limits_{d | n} \varphi(d) 是个积性函数。
- 当 n = 1 时,显然有 f(1) = 1。
- 当 n > 1 时,将 n 质因数分解,得:
综上所述,f(n) = \sum\limits_{d | n} \varphi(d) = n,Q.E.D
3.3.3:式 3
证明
Q.E.D
4:线性筛
线性筛,也叫 Euler 筛。可以在线性时间内筛出 1 \sim n 里的所有质数。相信大家都会。
4.1:线性筛筛积性函数
线性筛可以在线性时间内筛出大部分积性函数的前 n 项的函数值。
一般地,对于积性函数 f(x),若 f(p^c) 的值便于分析。则该函数的前 n 项的函数值可以被线性筛筛出来。
我们要多维护一个数组 \text{low}_i 表示:若 i 的最小质因子为 p_1,其次数为 c_1,则 \text{low}_i = p_1^{c_1}。
在线性筛的过程中,有特殊的两点:
- 若当前遇到了一个质数 p,则将 f(p), f(p^2), f(p^3), \cdots, f(p^c) 都计算出来。
- 在计算至少包含两个质因子的 i 对应的函数值时,由积性函数定义得 f(i) = f\left(\frac{i}{\text{low}_i}\right) \cdot f(\text{low}_i)。
这样就可以在线性时间内筛出一个积性函数的前 n 项了。对于一些简单的积性函数(例如 \varphi, \mu)就有更简单的筛法,不一定需要维护 \text{low}_i。
4.1.1:线性筛筛欧拉函数
- 设 p 为质数,若 p \mid n 且 p^2 \mid n,则 \varphi(n) = \varphi(\frac{n}{p}) \cdot p。
- 设 p 为质数,若 p \mid n 且 p^2 \nmid n,则 \varphi(n) = \varphi(\frac{n}{p}) \cdot (p - 1)。
const int SZ = 1e6;
int pClock, prime[SZ + 10], fac[SZ + 10];
int phi[SZ + 10];
void sieve(int N) {
phi[1] = 1;
for (int i = 2; i <= N; i ++) {
if (!fac[i]) fac[i] = i, prime[++ pClock] = i, phi[i] = i - 1;
for (int j = 1; j <= pClock; j ++) {
if (prime[j] > fac[i] || prime[j] > N / i) break;
fac[i * prime[j]] = prime[j];
phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
}
}
}4.1.2:线性筛筛莫比乌斯函数
- 设 p 为质数,若 p \mid n 且 p^2 \mid n,则 \mu(n) = 0。
- 设 p 为质数,若 p \mid n 且 p^2 \nmid n,则 \mu(n) = -\mu(\frac{n}{p})。
const int SZ = 1e6;
int pClock, prime[SZ + 10], fac[SZ + 10];
int mu[SZ + 10];
void sieve(int N) {
mu[1] = 1;
for (int i = 2; i <= N; i ++) {
if (!fac[i]) fac[i] = i, prime[++ pClock] = i, mu[i] = -1;
for (int j = 1; j <= pClock; j ++) {
if (prime[j] > fac[i] || prime[j] > N / i) break;
fac[i * prime[j]] = prime[j];
mu[i * prime[j]] = mu[i] * (i % prime[j] ? -1 : 0);
}
}
}4.1.3:线性筛筛各种积性函数
根据积性函数的特殊性质。利用 \text{low}_i 数组。可以在线性时间内筛出大部分积性函数的前 n 项的函数值。
请读者好好品味这段代码。
const int SZ = 1e6;
int pClock, prime[SZ + 10], low[SZ + 10];
int f[SZ + 10];
void sieve(int N) {
f[1] = 1;
for (int i = 2; i <= N; i ++) {
if (!low[i]) {
prime[++ pClock] = i;
long long x = i;
int c = 1;
while (x <= N) {
low[x] = x;
// calculate f(x)
x *= i, c ++;
}
}
for (int j = 1; j <= pClock; j ++) {
if (prime[j] > N / i) break;
if (i % prime[j] == 0)
low[i * prime[j]] = low[i] * prime[j];
else
low[i * prime[j]] = prime[j];
int num = i * prime[j];
f[num] = f[num / low[num]] * f[low[num]];
if (i % prime[j] == 0) break;
}
}
}4.2:例题选讲
4.2.1:【日常训练】挺好序列
Description
定义一个长度为 n 的挺好序列 a_1, a_2, \cdots, a_n,满足:对于 \forall i \in [1, n],都有 a_i | A。
定义一个长度为 n 的挺好序列 a_1, a_2, \cdots, a_n 的价值为 \gcd(a_1, a_2, \cdots, a_n, B),其中 B 为定值。
给出三个正整数 n, m, B。定义 f(x) 为 A = x 时所有挺好序列的价值和。请你求出:
答案对 998244353 取模。
数据范围:1 \leq n \leq 10^{18},1 \leq m \leq 2 \times 10^7,1 \leq B \leq 10^{18}。
时空限制:3000 \ \text{ms} /512 \ \text{MiB}。
Solution
结论
f(x) 是积性函数。
证明
考虑任意互质的正整数对 x, y。
设序列 a_1, a_2, \cdots, a_n 是 A = x 时的某个挺好序列,设序列 b_1, b_2, \cdots, b_n 是 A = y 时的某个挺好序列。
考虑生成序列 c_1, c_2, \cdots, c_n,其中 c_i = a_ib_i,显然该序列是 A = xy 时的某个挺好序列。
关注序列 c 的价值。因为 x, y 互质,所以 a_i, b_i 也一定互质。在唯一分解角度下观察,显然有:
故序列 c 的价值为序列 a, b 的价值之积。
回到积性函数的讨论上。f(x) \cdot f(y) 的每一项,相当于是从 f(x) 与 f(y) 各选一项的乘积。故 f(x) \cdot f(y) 是 A = xy 时所有挺好序列的价值和。
所以 f(xy) = f(x) \cdot f(y),所以 f(x) 为积性函数。
Q.E.D
注意到 1 \leq m \leq 2 \times 10^7,可以考虑线性筛。按照上文「4.1.3:线性筛筛积性函数」的内容。现在要对于任意一个质数 p,如何求出 f(p^c)。
对于一个质数 p,令 d 为满足 p^x \mid B 的最大的 x。可以简单分类讨论一下,不难得出:
- 当 c \leq d 时:
- 当 c > d 时:
求出 f(p), f(p^2), \cdots, f(p^c) 后,灵活运用线性筛即可求出 f(x) 的前 m 项,那么 \sum\limits_{i = 1}^m f(i) 就直接算即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long s64;
int qpow(int a, s64 b, int p) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = 1ll * ans * a % p;
a = 1ll * a * a % p;
}
return ans;
}
const int SZ = 2e7;
const int mod = 998244353;
void add(int &x, const int &y) {
x += y;
if (x >= mod) x -= mod;
}
void dec(int &x, const int &y) {
x -= y;
if (x < 0) x += mod;
}
s64 n, B;
int m;
int pClock, prime[SZ + 10], low[SZ + 10];
int f[SZ + 10];
int get_top(int p) {
int num = B, cnt = 0;
while (num % p == 0) num /= p, cnt ++;
return cnt;
}
int power[100];
void sieve(int N) {
for (int i = 1; i < 100; i ++) power[i] = qpow(i, n, mod);
f[1] = 1;
for (int i = 2; i <= N; i ++) {
if (!low[i]) {
prime[++ pClock] = i;
int d = get_top(i);
s64 x = i;
int c = 1;
while (x <= N) {
low[x] = x;
if (c <= d) {
for (int j = 0, g = 1; j <= c; j ++, g = 1ll * g * i % mod) {
int rate = power[c - j + 1]; dec(rate, power[c - j]);
add(f[x], 1ll * g * rate % mod);
}
} else {
int g = 1;
for (int j = 0; j < d; j ++, g = 1ll * g * i % mod) {
int rate = power[c - j + 1]; dec(rate, power[c - j]);
add(f[x], 1ll * g * rate % mod);
}
add(f[x], 1ll * g * power[c - d + 1] % mod);
}
x *= i, c ++;
}
}
for (int j = 1; j <= pClock; j ++) {
if (prime[j] > N / i) break;
if (i % prime[j] == 0)
low[i * prime[j]] = low[i] * prime[j];
else
low[i * prime[j]] = prime[j];
int num = i * prime[j];
f[num] = 1ll * f[num / low[num]] * f[low[num]] % mod;
if (i % prime[j] == 0) break;
}
}
}
int main() {
scanf("%lld%d%lld", &n, &m, &B);
sieve(m);
int ans = 0;
for (int i = 1; i <= m; i ++) add(ans, f[i]);
printf("%d\n", ans);
return 0;
}5:莫比乌斯反演
已知两个数论函数 f, g 满足:
则:
证明
已知条件等价于:
两边同卷 \mu 可得:
QED。
5.1:例题选讲
5.1.1:经典问题
Description
给出一个正整数 n,求有多少个长度为 n,循环节长度也恰好为 n 的小写字符串。
数据范围:1 \leq n \leq 10^9。
Solution
设长度为 n 的小写字符串有 f(n) 个;设长度为 n,循环节长度也恰好为 n 的小写字符串有 g(n) 个。
显然有:
以及:
根据莫比乌斯反演,可得:
5.1.2:【Luogu P2522】「HAOI2011」Problem b
Description
给出五个正整数 a, b, c, d, k,请你求出:
共 T 组询问。
数据范围:1 \leq T, k \leq 5 \times 10^4,1 \leq a \leq b \leq 5 \times 10^4,1 \leq c \leq d \leq 5 \times 10^4。
时空限制:2500 \ \mathrm{ms} / 250 \ \mathrm{MiB}。
Solution
记 \text{calc}(n, m) 为:
简单容斥可得,答案为:
考虑这样一个 \text{calc}(n, m) 要怎么求,注意到 \gcd(i, j) = k 与 \gcd\left(\frac{i}{k}, \frac{j}{k}\right) = 1 是等价的,故原式化为:
利用 \epsilon = \mu \ast 1 反演,得:
交换枚举顺序,考虑先枚举 d。要使得 d \mid \gcd(i, j),只需要让 d \mid i 且 d \mid j 即可,故答案化为:
上式就比较好处理了。线性筛筛出莫比乌斯函数,求一遍莫比乌斯函数的前缀和,然后直接上数论分块。
实现上,可以先令 n \gets \left\lfloor \frac{n}{k} \right\rfloor, m \gets \left\lfloor \frac{m}{k} \right\rfloor,这样就比较好做了。
时间复杂度 \mathcal{O}(N + T\sqrt{N}),其中 N 表示输入数据上界。
5.1.3:【Luogu P1829】「国家集训队」Crash 的数字表格
Description
给出两个正整数 n, m,请你求出:
答案对 20101009 取模。
数据范围:1 \leq n, m \leq 10^7。
时空限制:2000 \ \mathrm{ms} / 500 \ \mathrm{MiB}。
Solution
不难发现原式为:
令 d = \gcd(i, j),考虑交换枚举顺序:
将 i 和 j 中的 d 提取出来,得:
记:
考虑化简 F(n, m):
记:
则:
可以线性筛一下,然后数论分块。当 n, m 同阶时,计算 F(n, m) 是 \mathcal{O}(\sqrt{n}) 的。
回到本题,可得答案为:
然后这个式子也可以数论分块做,本质上是一个数论分块套数论分块。
线性筛的复杂度是 \Theta(n) 的。数论分块套数论分块的复杂度是 \mathcal{O}(n^{\frac{3}{4}})。
于是这题就这样做完了。
关于「数论分块套数论分块」复杂度的证明
原问题中最后计算答案的式子是一个二维数论分块套二维数论分块,看起来不太爽。我们把它替换成一个一维数论分块套一维数论分块,大概是这样:
其中,计算 F(n) 的复杂度是 \mathcal{O}(\sqrt{n}) 的。考虑证明上式的复杂度。
可以分类讨论一下:
- 当 d \leq \sqrt{n} 时,最劣的情况是每一个 \left\lfloor \frac{n}{d} \right\rfloor 互不相同,故此部分对复杂度的贡献为:
- 当 d > \sqrt{n} 时,注意到 \left\lfloor \frac{n}{d} \right\rfloor 的值会均会落在区间 [1, \sqrt{n}] 中,最劣的情况是 \left\lfloor \frac{n}{d} \right\rfloor 的值将 [1, \sqrt{n}] 里的所有数都取过一遍,故此部分对复杂度的贡献为:
简单积分近似一下:
根据微积分基本定理,设 H(x) = \frac{2}{3} x^{\frac{3}{2}} + n^{\frac{1}{2}} \cdot 2x^{\frac{1}{2}},有 H'(x) = x^{\frac{1}{2}} + \left( \frac{n}{x} \right)^{\frac{1}{2}}。则:
故数论分块套数论分块的复杂度是 \mathcal{O}(n^\frac{3}{4}) 的。
5.1.4:【Luogu P2257】YY 的 GCD
Description
给出两个正整数 n, m,请你求出满足 1 \leq i \leq n 且 1 \leq j \leq m 的所有数对 (i, j) 中,满足 \gcd(i, j) 为质数的数对有多少个。
共 Q 组数据。
数据范围:1 \leq Q \leq 10^4,1 \leq n, m \leq 10^7。
时空限制:4000 \ \mathrm{ms} / 500 \ \mathrm{MiB}。
Solution
为了方便叙述,设质数集为 \mathbb{P}。
注意到答案为:
考虑继续化简,令 T = pd,则上式化为:
记 H(n) = \sum\limits_{p | n, p \in \mathbb{P}} \mu(\frac{n}{p}),则原式化为:
考虑预处理出 H(n)。可以使用 “ 倍数法 “,对于每个质数 p,让其去贡献它的每一个倍数 T,稍微卡卡常也可以过。更高明的做法是挖掘 H(n) 的一些性质,然后使用线性筛将 H(n) 筛出来,这里直接给出结论:
预处理出 H(n) 后再处理出它的前缀和。这样就可以配合数论分块求出答案的值了。
时间复杂度 \mathcal{O}(n + Q\sqrt{n})。
5.1.5:【LOJ #6627】「XXOI 2019」等比数列三角形
Description
给出一个正整数 n。请你求出:有多少个合法的三角形,满足三边都是 \leq n 的整数,且三边成等比数列。
数据范围:1 \leq n \leq 10^{12}。
时空限制:1000 \ \mathrm{ms} / 256 \ \mathrm{MiB}。
Solution
枚举公差,将公差表示成一个既约分数 k = \frac{p}{q} \geq 1 的形式,也就是说我们要保证 \gcd(p, q) = 1。
对于任意的一个三角形,不妨设三边中的最短边为 x,则三边为 x, kx, k^2x。
考虑公差 k = \frac{p}{q} 有一些什么限制:
- 需要满足三角形的 “ 两边之和大于第三边 “,即:
设 e = \frac{1 + \sqrt 5}{2},根据上面的两条限制,不难得出 q 关于 p 的取值范围:
- 需要满足三角形的三边都是整数,即:
由于 q^2 \mid x,可设 i = \frac{x}{q^2},则答案为:
记 S(n, p) = \sum\limits_{i = 1}^n [\gcd(i, p) = 1],考虑化简该函数:
回到问题中,答案化为:
使用 “ 倍数法 “,计算出函数 g(p) = S(p, p) - S(\left\lceil \frac{p}{e} \right\rceil - 1, p),然后直接算即可。
时间复杂度 \mathcal{O}(\sqrt{n} \log \sqrt{n})。
6:杜教筛
有时候,我们需要快速地对一些数论函数求前缀和,甚至是需要在低于线性时间的复杂度内求解。这时可以利用杜教筛来求出这些前缀和。
一般地,给出一个数论函数 f(x),你需要求出 S(n) = \sum\limits_{i = 1}^n f(i)。
注意到,对于任意一个数论函数 g,必定会满足:
故有:
此时我们得到了一个 S(n) 关于 S(\left\lfloor \frac{n}{i} \right\rfloor) 的递推式。若 f \ast g 与 g 的前缀和都较好处理的话,就可以考虑使用数论分块来处理上面的递推式,较短时间内求出 S(n),因此找到一个合适的数论函数 g 是关键。
如果直接使用数论分块做上面的递推式,根据 \left\lfloor \frac{n}{d} \right\rfloor 的取值进行分段。 不考虑递归的情况下,单纯去处理一个 S(n) 的复杂度是 \mathcal{O}(\sqrt{n}) 的,递归下去的复杂度为低阶小量 o(\sqrt{n}),故计算 S(n) 的复杂度为:
简单积分近似一下:
可以积分近似证明,先线性筛预处理出 f(x) 的前 n^\frac{2}{3} 项,可以取得杜教筛的理论最优复杂度 \mathcal{O}(n^\frac{2}{3})。
对于一些较大的 n,需要使用 std::map 来存下对应的值(记忆化),方便以后使用时直接计算出结果。
6.1:例题选讲
6.1.1:【Luogu P4213】Sum
Description
给出一个正整数 n,请你求出:
数据范围:1 \leq n < 2^{31}。
时空限制:2000 \ \mathrm{ms} / 512 \ \mathrm{MiB}。
Solution
莫比乌斯函数前缀和
注意到 \mu \ast 1 = \epsilon,则考虑使用常数函数 1(n) = 1 来构造递推式:
然后直接筛即可。
欧拉函数前缀和
注意到 \varphi \ast 1 = \text{ID},则考虑使用常数函数 1(n) = 1 来构造递推式:
然后直接筛即可,但其实更好的做法是莫比乌斯反演。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
const int SZ = 1e6;
int n;
int m, prime[SZ + 10], fac[SZ + 10], mu[SZ + 10];
int Smu[SZ + 10];
void sieve(int N) {
mu[1] = 1;
for (int i = 2; i <= N; i ++) {
if (!fac[i]) fac[i] = i, prime[++ m] = i, mu[i] = -1;
for (int j = 1; j <= m; j ++) {
if (prime[j] > fac[i] || prime[j] > N / i) break;
fac[i * prime[j]] = prime[j];
mu[i * prime[j]] = mu[i] * (i % prime[j] ? -1 : 0);
}
}
for (int i = 1; i <= N; i ++)
Smu[i] = Smu[i - 1] + mu[i];
}
std::map<int, int> Smu_buc;
int Smu_calc(int n) {
if (n <= SZ) return Smu[n];
if (Smu_buc.count(n)) return Smu_buc[n];
int cur = 1;
for (long long x = 2, nx; x <= n; x = nx + 1) {
nx = n / (n / x);
cur -= (nx - x + 1) * Smu_calc(n / x);
}
return Smu_buc[n] = cur;
}
void work() {
scanf("%d", &n);
long long ans1 = 0;
int ans2 = Smu_calc(n);
for (long long x = 1, nx; x <= n; x = nx + 1) {
nx = n / (n / x);
ans1 += 1ll * (Smu_calc(nx) - Smu_calc(x - 1)) * (n / x) * (n / x);
}
ans1 = (ans1 + 1) / 2;
printf("%lld %d\n", ans1, ans2);
}
int main() {
sieve(SZ);
int T;
scanf("%d", &T);
while (T --) work();
return 0;
}6.1.2:【Luogu P3768】简单的数学题
Description
给出一个正整数 n,请你求出:
答案对给定的质数 p 取模。
数据范围:1 \leq n \leq 10^{10},5 \times 10^8 \leq p \leq 1.1 \times 10^9。
时空限制:4000 \ \mathrm{ms} / 256 \ \mathrm{MiB}。
Solution
利用 \varphi \ast 1 = \text{ID} 反演,得:
记 F(n) = \sum\limits_{i = 1}^n i = \frac{n(n + 1)}{2},则答案化为:
考虑使用数论分块处理上式,现在的问题是要求出函数 H(n) = \varphi(n) \cdot n^2 的前缀和,考虑杜教筛。
线性筛的部分相信大家都会,主要是讨论构造 S(n) = \sum\limits_{i = 1}^n H(i) 关于 S(\left\lfloor \frac{n}{i} \right\rfloor) 递推式的部分。
注意到恒等函数 \text{ID}_2,考虑将 H 与 \text{ID}_2 卷在一起:
于是可以得到 H \ast \text{ID}_2 = \text{ID}_3,我们发现 \text{ID}_2 与 \text{ID}_3 的前缀和都可以直接 \Theta(1) 计算(实在记不清楚公式的话,直接上拉格朗日插值吧),于是我们就可以得到 S(n) 的递推式:
直接上数论分块即可。
6.1.3:【BZOJ #4804】欧拉心算(加强版)
Description
给出两个正整数 n, m,请你求出:
数据范围:1 \leq n, m \leq 10^9。
时空限制:1500 \ \mathrm{ms} / 512 \ \mathrm{MiB}。
Solution
记 T = pd,则式子化简为:
设 g = \varphi \ast \mu(这里的 \ast 是狄利克雷卷积,下文同),则式子化简为:
可以用数论分块处理上式,现在的问题是要求 g 的前缀和。可以考虑杜教筛,设:
记 d = 1 \ast 1,其中函数 1(n) = 1,显然函数 d 为约数个数函数。
那么可以得到 S(n) 有关 S\left(\left\lfloor\frac{n}{d}\right\rfloor\right) 的递推式:
化简:
约数个数函数前缀和 \sum\limits_{i = 1}^h d(i) 即为 \sum\limits_{i = 1}^h \left\lfloor\frac{h}{i}\right\rfloor。直接用数论分块求解,复杂度较大。运用类似杜教筛的方法处理,具体地:
- 对于 x \leq n^{\frac{2}{3}} 的部分:运用线性筛求解每个 S(x), \sum_{i = 1}^x d(i)
- 对于 x > n^{\frac{2}{3}} 的部分:运用数论分块求解 \sum_{i = 1}^x d(i),运用递推式求解 S(x)。
可以证明两部分的复杂度均为 \mathcal{O}(n^{\frac{2}{3}}),直接上数论分块即可。