模板及讲解
整数分块
求 $\sum_{i=1}^n \lfloor \frac ni \rfloor$。
显然可以暴力$O(n)$求。但是这里可以$O(\sqrt n)$ 求。
结论：对于所有的 $\lfloor \frac ni \rfloor$ 都是一段连续的块，并且块的端点可以被枚举。假设当前在 $i$ 处，那么 $\lfloor \frac ni \rfloor$的最后一个值在$\lfloor \frac{n}{\lfloor \frac ni \rfloor} \rfloor$
证明：设$\lfloor \frac ni \rfloor = \lfloor \frac n{i’} \rfloor=k$，并且$i’$为最大的位置。
设$i+d=i’$，$n=ik+p,n=(i+d)k+p’$
可得$p’=p-dk$，则$d_{max}= \lfloor \frac pk \rfloor$
那么$i’=i+d_{max}$
$$
=i+ \left \lfloor \frac pk \right \rfloor=i+\left\lfloor \frac {n\%i}{\left\lfloor \frac ni \right\rfloor} \right\rfloor=\left\lfloor i+ \frac {n\%i}{\left\lfloor \frac ni \right\rfloor} \right\rfloor=\left\lfloor \frac {i \cdot \left\lfloor \frac ni \right\rfloor}{\left\lfloor \frac ni \right\rfloor}+ \left\lfloor \frac {n\%i}{\left\lfloor \frac ni \right\rfloor} \right \rfloor \right\rfloor
$$
$$
= \left\lfloor \frac {i \cdot \left\lfloor \frac ni \right\rfloor+n-\left\lfloor \frac ni \right\rfloor \cdot i}{\left\lfloor \frac ni \right\rfloor} \right\rfloor= \left\lfloor \frac {n}{\left\lfloor \frac ni \right\rfloor} \right\rfloor
$$
得证。
易得$\lfloor \frac ni \rfloor$取值不超过$2\sqrt n$ 个，所以复杂度为$O(\sqrt n)$。
例题：Bzoj 1968
LL l = 1, r, ans = 0ll;
while (l <= n) {
r = (n / (n / l));
ans += (r - l + 1ll) * (n / l);
l = r + 1ll;
}
给出 $n, k$，求$\sum_{i=1}^n k \mod i$
$k \mod i= k -i \cdot \lfloor \frac ki \rfloor$，则$\sum_{i=1}^n k \mod i= \sum_{i=1}^n k -i \cdot \lfloor \frac ki \rfloor=nk-\sum^{n}_{i=1} i \cdot \lfloor \frac ki \rfloor$
发现右边是整除分块的形式，所以加一个等差数列求和公式计算即可。注意此题要判断一下$n,k$的大小。复杂度$O(\sqrt n)$
LL ans = 0ll, l = 1, r;
if (n > k) ans += (n - k) * k, n = k;
ans += n * k;
while (l <= n) {
r = min(n, (k / (k / l)));
ans -= (l + r) * (r - l + 1ll) / 2ll * (k / l);
l = r + 1ll;
}
此题有升级版,Blog，$T(T \leq 10^6)$组询问$n(n \leq 10^6)$。此时用整除分块会炸。考虑$i \cdot \lfloor \frac ki \rfloor$的意义就是因数和。所以线性筛因数和即可。预处理前缀和后$O(1)$ 处理询问。
线性筛积性函数
线性筛积性函数考虑两个
第一个是$f(p), p$为质数是的取值怎么$O(1)$算
第二个是$f(p^x), p$为质数是的取值怎么$O(1)$算，也就是说我们需要从$f(p^x)$转到$f(p^{x+1})$怎么求
第一个：在某数为质数时需要$O(1)$算出函数值
第二个：线性筛是用最小质因数去筛数，所以对于被筛的数在$p|i$时只需要考虑$f(p^x)$转到$f(p^{x+1})$怎么求
而$gcd(i,p)=1$时利用积性函数性质进行求解即可。
莫比乌斯函数
若 $i=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，那么有莫比乌斯函数
$$
\mu(i)=
\begin{cases}
1&,i=1 \\
(-1)^k&,\forall a_k=1 \\
0&,\exists a_k\gt1
\end{cases}
$$
性质
1、莫比乌斯函数是积性函数
$μ(a)μ(b)=μ(ab),a⊥b$
运用此性质可以线性筛莫比乌斯函数。
2
$$
\sum_{d\mid n}\mu(d) = [n = 1]
$$
证明：(二项式定理)
设$n$有$k$种因子。则
$$
\sum_{d\mid n}\mu(d)=\sum_{i=0}^kC^i_k(-1)^i1^{k-r}=[n=1]
$$
线性筛莫比乌斯函数
时间复杂度 $ O(n) $。
有更优秀的杜教筛。
mu[1] = 1, vis[1] = 1; // mu[1] = 1
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1; // 奇数个 mu[i] = -1
for (int j = 1; j <= tot && (LL)i * (LL)pri[j] <= (LL)n; ++j) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) {
mu[i * pri[j]] = 0; // 一个质因子多个 mu[i] = 0
break;
} else mu[i * pri[j]] = -mu[i]; // 积性函数
}
}
莫比乌斯反演
定义
$g(n)$和$f(n)$是定义在非负整数集合上的两个函数
1、当$$g(n)=\sum_{d|n}f(d)$$
那么有莫比乌斯反演
$$
f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})
$$
2、当$g(i)=\sum^{\frac ni}_{d=1}f(d \cdot i)$
那么有莫比乌斯反演
$$
f(i)=\sum_{d=1}^{\frac ni}g(d \cdot i)\mu(d)
$$
证明
$$
\sum_{d|n}\mu(d)g(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}f(i)=\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}\mu(d)=f(n)
$$
证明都是用将 $\mu(k)$ 提后然后根据性质1判断。
变形
欧拉函数变形
$$
\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]=\sum_{i=1}^n\sum_{k\mid i,k\mid n}\mu(k)=\sum_{k\mid n}\mu(k)\lfloor\frac nk\rfloor
$$
运用
求 $\gcd = k$ 的个数
例题：Bzoj 2301
题意：给定$a, b, c, d, k$, 求
$$
\sum_{i=a}^{b} \sum_{j=c}^{d} [\gcd(i,j)=k]
$$
(下面默认$n \leq m$, 不满足则交换)
解：
我们可以将答案分成几个部分求解，然后$ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)$
依题意设出$f(k)$为$gcd(i,j)=k$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
但是这个并不好求，看见两个求和符号，我们可以想到用莫比乌斯反演来求解。
显然用变形后的两个式子，我们就可以设$g(k)$为$k|gcd(i,j)$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
$g(k)$非常好算，$g(k)=\lfloor \frac n{k} \rfloor \lfloor \frac m{k} \rfloor$
而显然$g(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} f(ki)$
那么可以莫比乌斯反演
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \lfloor \frac n{kd} \rfloor \lfloor \frac m{kd} \rfloor
$$
换元$\lfloor \frac nk \rfloor$，整除分块即可。
注意有$n,m$的整除分块是取两者最小值，复杂度也是有保证的。
求 $\gcd(i,j)$ 的和
例题：Bzoj 2005
题意：
给定$n,m$，求
$$
\sum_{i=1}^n\sum_{j=1}^m \gcd(i,j)
$$
按照套路反演以后得到
$$
\sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac nd \rfloor} \mu(i) \lfloor \frac n{di} \rfloor \lfloor \frac m{di}\rfloor
$$
然后我们设$T=di$，则
$$
\sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T} \mu(d) \lfloor \frac Tk \rfloor
$$
设$h(T)=\sum_{d|T} \mu(d) \lfloor \frac Tk \rfloor$，则可以线性筛。
也可以发现这就是欧拉函数，直接筛欧拉函数即可。
求 $\gcd(i,j)^k$ 的和
例题：BZOJ 4407
题意：
给定$n,m,k$，求
$$
\sum_{i=1}^n\sum_{j=1}^m \gcd(i,j)^k \mod (10^9+7)
$$
按照套路反演以后得到
$$
\sum_{d=1}^n d^k \sum_{i=1}^{\lfloor \frac nd \rfloor} \mu(i) \lfloor \frac n{di} \rfloor \lfloor \frac m{di}\rfloor
$$
此时我们发现可以分块套分块达到复杂度$O(n)$单次询问。
但是还是不够，那么继续变形
设$T=di$，则
$$
\sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T} d^k \mu(\frac Td)
$$
设$f(T)=\sum_{d|T}d^k \mu(\frac Td)$，发现$d^k$和$\mu(k)$都是积性函数，所以乘积也是积性函数，所以我们可以线性筛$O(n)$算这个积性函数值。
如何线性筛？
线性筛积性函数考虑两个
第一个是$f(p), p$为质数时的取值怎么$O(1)$算
第二个是$f(p^x), p$为质数时的取值怎么$O(1)$算，也就是说我们需要从$f(p^x)$转到$f(p^{x+1})$怎么求
考虑将$T$质因数分解，那么对于每个$p_i$
$$
f(p_i^{x_i})=\sum_{d|p_i^{x_i}}d^k\mu(\frac{p_i^{x_i}}d)
$$
因为有$\mu$的存在，只需要考虑$d=p_i^{x_i}$和$d=p_i^{x_i-1}$的情况，则原式化为
$$
f(p_i^{x_i})=\mu(p_i) \cdot p_i^{k(x_i-1)} + \mu(1) \cdot p_i^{x_ik}
$$
即
$$
f(p_i^{x_i}) = p_i^{x_ik} - p_i^{k(x_i-1)}
$$
$$
f(p_i^{x_i}) = p_i^{k(x_i-1)}(p_i^k-1)
$$
这个式子可以方便解决$f(p^x), p$为质数时的取值
对于第一个，$f(p)=\mu(1) \cdot p^k + \mu(p) \cdot 1^k=p^k-1$
那么这样就可以线筛了。
求 $\operatorname{lcm}(i,j)$ 的和
例题：BZOJ 2154
题意：给定$n, m$，求
$$
\sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i, j)
$$
化为$\gcd$式子
$$
\sum_{d=1}^n d \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{\gcd(i,j)} \\
\sum_{d=1}^n d \sum_{i=1}^{\lfloor \frac nd \rfloor}\sum_{j=1}^{\lfloor \frac md \rfloor}ij \cdot [\gcd(i,j)=1]
$$
设
$$
f(n,m)=\sum_{i=1}^n \sum_{j=1}^m ij \cdot [\gcd(i,j)=1] \\
=\sum_{d=1}^n \sum_{d|i} \sum_{d|j} \mu(d) \cdot d^2 \sum_{i=1}^{\lfloor \frac nd \rfloor}\sum_{j=1}^{\lfloor \frac md \rfloor}ij
$$
设 (两个等差数列相乘)
$$
g(n,m)=\sum_{i=1}^n \sum_{j=1}^m ij =\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}
$$
则
$$
f(n,m)=\sum_{d=1}^n \mu(d) \cdot d^2 \cdot g(\lfloor \frac nd \rfloor, \lfloor \frac md \rfloor)
$$
即原式为
$$
\sum_{d=1}^m d \cdot f(\lfloor \frac nd \rfloor, \lfloor \frac md \rfloor)
$$
计算$f(n,m)$时整除分块，计算答案时整除分块，时间复杂度$O(n+m)$
求$f(gcd(i,j))$的和
例题：BZOJ 3529
题意：给定多组$n,m,a$，设$d_1(n)$为$n$约数和，求
$$
\sum_{i=1}^n \sum_{j=1}^m d_1(\gcd(i, j))
$$
并且满足$d_1(\gcd(i, j)) \leq a$
不考虑$a$的限制，枚举约数
$$
\sum_{d=1}^n \sum_{i=1}^n \sum_{j=1}^m d_1(d)[gcd(i,j)=d])
$$
发现$d_1(d)$与$i,j$无关，移到前面
$$
\sum_{d=1}^n d_1(d) \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d])
$$
将后面用反演套路化简，得
$$
\sum_{d=1}^n d_1(d) \sum_{k=1}^{\lfloor \frac nd \rfloor} \mu(k) \lfloor \frac n{kd} \rfloor \lfloor \frac m{kd} \rfloor
$$
设$T=kd$，则
$$
\sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T}d_1(d) \mu(\frac Td)
$$
如果没有$a$的限制，则线性筛后面的函数即可。
考虑$a$的限制。
只有$d_1(x) \leq a$的才会有贡献。
所以将$d_1(x)$从小到大排序，将询问离线后按$a$从小到大排序
每次按照$a$的单增补齐到$a$，补齐即枚举$x$的倍数进行增加。
维护一个单调修改区间查值的数据结构，用树状数组维护之。
时间复杂度：$O(n\log ^2 n + q \sqrt n \log n)$
总结
莫比乌斯反演一般是
1、两个求和符号
2、用反演公式设出与所求的那个函数符合的函数，然后导出基本式子
3、用技巧(换元、内层外移、观察、莫比乌斯函数容斥性等)来化简式子
4、最后的答案整除分块，必要时将与外层枚举变量无关的式子证明是积性函数来线性筛，无法证明则打表验证，重点关注质数，质数的幂的值
莫比乌斯反演的套路
1、换元，比如设$T=kd$
2、内层外移 (换元后、枚举约数$\Leftrightarrow$直接枚举)
3、设新函数线性筛/反演/处理：比如设$h(T)=\sum_{d|T} \mu(d) \lfloor \frac nk \rfloor$
4、观察法：一般是观察$\mu$的取值造成的影响
5、化布尔式为$\mu$式子 (例子：$[n=1] \Leftrightarrow \sum_{d|n} \mu(d)$)
6、构造$[\gcd(i,j)=k]$反演
Dirichlet 卷积
常见的完全积性函数
1、$\epsilon(x)$：Dirichlet卷积的乘法单位元，完全积性。$\epsilon(x) = [x = 1]$
2、$I(n)$：恒等函数，完全积性。$I(n)=1$
3、$id(n)$：单位函数，完全积性。$id(n)=n$
4、$id^k(n)$：幂函数，完全积性。$id^k(n)=n^k$
定义
数论函数$f$和$g$的Dirichlet卷积定义为
$$
(f∗g)(n)=\sum_{d|n}f(d) g(\frac nd)
$$
满足交换律、结合律、分配律，证明此处略去。
性质
1、如果 $f$ 和 $g$ 均为积性函数，那么 $f∗g$ 一定也为积性函数。
2、任何数论函数$f$卷上$I$代表$\sum\limits_{d|n} f(d)$，卷上$id$代表$\sum\limits_{d|n} f(d) \cdot \frac di $，$id^k$类似
3、任何数论函数$f$卷上$\epsilon$还是原函数$f$，所以就验证了$\epsilon$是单位元。
4、$\mu * I = \epsilon$
根据$\sum \limits_{d|n} {\mu(d)} = [n =1]$即可证明。
5、$\varphi * I = id$
根据$\sum \limits_{d | n} {\varphi(d) = n}$即可证明。
6、$\varphi = id * \mu$ ($\mu$与$\varphi$关系)
由$\varphi * I = id$，两边卷$\mu$
$$\varphi * I * \mu = id * \mu$$
则
$$\varphi = id * \mu$$
7、$\frac{\varphi(n)}{n} = \sum \limits_{d | n} {\frac{\mu(d)}{d}}$ ($\mu$与$\varphi$关系)
由$\varphi = id * \mu$
$$\varphi(n) = \sum \limits_{d | n} {\mu(d) \times \frac{n}{d}}$$
将两边同时除以 $n$
$$\frac{\varphi(n)}{n} = \sum \limits_{d | n} {\frac{\mu(d)}{d}}$$
证明莫比乌斯反演
根据定义
$$
f = g * I
$$
两边卷上$\mu$
$$
f * \mu = g * I * \mu
$$
由$\mu * I = \epsilon$
$$
f * \mu = g * \epsilon \\
g = f * \mu
$$
得证。
杜教筛
模板题：Bzoj 3944 杜教筛Sum
给定一个正整数$n$，求
$$
\sum_{i=1}^n \varphi(i) \\
\sum_{i=1}^n \mu(i)
$$
设$f$是我们要求前缀和的积性函数，设$S(n)=\sum_{i=1}^n$
找一个$g$卷上$f$
$$
\sum_{i=1}^n (f * g)(n)
$$
Dirichlet 卷积定义转化
$$
\sum_{i=1}^n \sum_{d|i} f(d)g(\frac id)
$$
先枚举$d$
$$
\sum_{d=1}^n g(d) \sum_{i=1}^{\lfloor \frac nd \rfloor} f(i)
$$
用$S$改写
$$
\sum_{d=1}^n g(d)S(\lfloor \frac nd \rfloor)
$$
考虑 (两个前缀和相减)
$$
g(1)S(n)=\sum_{i=1}^n(f * g)(n) - \sum_{i=2}^n g(i)S(\lfloor \frac ni \rfloor)
$$
那么找到一个合适的$g$，能快速求出$f * g$的前缀和，则就能递归+整除分块快速求出$f$的前缀和。
这个算法复杂度$O(n^{\frac 34})$
预处理出前$m=n^{\frac 23}$个前缀和，可以使复杂度变为$O(n^{\frac 23})$
(这个也不是限定死的，可以尽量往大开)
1、求$\sum\limits_{i=1}^n \varphi(i)$
由$\varphi * I = id$，得
$$
\sum_{i=1}^n \varphi(i)=\frac{n(n + 1)}{2}-\sum_{i=2}^n \varphi(\lfloor \frac ni \rfloor)
$$
2、求$\sum\limits_{i=1}^n \mu(i)$
由$\mu * I = \epsilon$，得
$$
\sum_{i=1}^n \mu(i)=1-\sum_{i=2}^n \mu(\lfloor \frac ni \rfloor)
$$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL N = 5000000;
int vis[N + 5], pri[400000 + 5], tot;
LL mu[N + 5], phi[N + 5];
LL T;
map<int, LL > ansphi, ansmu;
LL getphi(int n) {
if (n <= N) return phi[n];
if (ansphi[n]) return ansphi[n];
LL ret = 1ll * n * (n + 1ll) / 2ll;
int l = 2;
while (l <= n) {
int r = n / (n / l);
ret -= 1ll * (r - l + 1ll) * getphi(n / l);
if (r == 2147483647) break ;
l = r + 1;
}
return ansphi[n] = ret;
}
LL getmu(int n) {
if (n <= N) return mu[n];
if (ansmu[n]) return ansmu[n];
LL ret = 1ll; // ²»ÊÇ [n=1]
int l = 2;
while (l <= n) {
int r = n / (n / l);
ret -= 1ll * (r - l + 1ll) * getmu(n / l);
if (r == 2147483647) break ;
l = r + 1;
}
return ansmu[n] = ret;
}
void init() {
ms(vis, 0), ms(pri, 0), tot = 0, ms(mu, 0), ms(phi, 0);
mu[1] = 1, phi[1] = 1;
for (int i = 2; i <= N; ++i) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1, phi[i] = i - 1;
for (int j = 1; j <= tot && 1ll * pri[j] * i <= 1ll * N; ++j) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
mu[i * pri[j]] = 0;
phi[i * pri[j]] = phi[i] * pri[j];
break ;
} else mu[i * pri[j]] = mu[i] * mu[pri[j]], phi[i * pri[j]] = phi[i] * phi[pri[j]];
}
}
for (int i = 2; i <= N; ++i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}
void clean() {
}
int solve() {
clean();
scanf("%lld", &T);
while (T--) {
LL n; scanf("%lld", &n);
printf("%lld %lld\n", getphi(n), getmu(n));
}
return 0;
}
}
int main() {
flyinthesky::init();
flyinthesky::solve();
return 0;
}
