浅谈积性函数
bbbzzx
·
·
算法·理论
定义
参见数论基础。
整除分块
许多题目是与积性函数有关的求和题，往往需要用整除分块降低复杂度，这也是杜教筛的思路。
整除分块，又叫数论分块，顾名思义就是通过分块的思想来计算，先来看以下这个例子，求：
\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor
首先我们令 n=8，\lfloor \frac{n}{i} \rfloor 的数列是这样的：
8,4,2,2,1,1,1,1
只有 4 种取值，于是我们考虑利用这些重复的数减少计算量。
首先证明取值的个数是 O(\sqrt n) 的：
$i>\sqrt n$，则有 $\frac{n}{i}<\sqrt n$，取值数也是 $O(\sqrt n)$ 的。
注意到相同的取值总是形成一个连续块，于是我们利用这个性质来分块。
设块的左端点为 $L$，右端点为 $R$，由块与块之间连续可得 $L=R_{last}+1$，问题来了，已知 $L$，如何求 $R$？
首先我们知道块内取值是相同的，设 $val=\lfloor \frac{n}{L} \rfloor$，一定有 $R\times val \leq n$，由于 $R$ 是最大的，可得 $R=\lfloor \frac{n}{\lfloor \frac{n}{L} \rfloor} \rfloor$。
于是我们可以通过分块 $O(\sqrt n)$ 计算值了。
```cpp
inline int solve(int n){
int ans=0,L,R;
for(L=1;L<=n;L=R+1){
R=n/(n/L);
ans+=(R-L+1)*(n/L);
}
return ans;
}
```
### 例 1
P3935
求：
$$\sum_{i=1}^n d(i)$$
其中 $d(n)$ 为 $n$ 的因数个数。
发现 $d(n)$ 为积性函数，于是直接杜教筛，当然要是这么做家里要请高人了。
考虑枚举每个数作因数的次数，显然两者是等价的，于是原式等于：
$$\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$$
这不就是上面的例子吗，直接套作。
### 例 2
P2260
求：
$$\sum_{i=1}^n \sum_{j=1}^m (n \bmod i)(m \bmod j),i \neq j$$
$$=\sum_{i=1}^n (n \bmod i) \sum_{j=1}^m (m \bmod j) - \sum_{i=1}^{\min(n,m)} (n \bmod i)(m \bmod i)$$
考虑前一项，
$$\sum_{i=1}^n (n \bmod i)$$
$$=\sum_{i=1}^n (n-i \lfloor \frac{n}{i} \rfloor)$$
$$n^2-\sum_{i=1}^n i \lfloor \frac{n}{i} \rfloor$$
后面这个就可以用整除分块来做了，一个等差数列求和对吧。
考虑后一项，不妨设 $n \leq m$，原式等于：
$$\sum_{i=1}^n （nm-ni \lfloor \frac{m}{i} \rfloor -mi \lfloor \frac{n}{i} \rfloor+i^2 \lfloor \frac{n}{i} \rfloor\lfloor \frac{m}{i} \rfloor)$$
展开得：
$$n^2m+\sum_{i=1}^n(-ni \lfloor \frac{m}{i} \rfloor -mi \lfloor \frac{n}{i} \rfloor+i^2 \lfloor \frac{n}{i} \rfloor\lfloor \frac{m}{i} \rfloor)$$
后面这一项也可以用整除分块来做，至于 $i^2$ 项我们可以用平方和公式 $O(1)$ 计算。
$$\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$$
总时间复杂度 $O(\sqrt n)$。
# 欧拉函数
## 定义及性质
$\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]$。
- $\varphi(1)=1$，若 $n \in P$，$\varphi(n)=n-1$。
- 欧拉定理：若 $\gcd(a,p)=1$，$a^{\varphi(p)} \equiv 1 \pmod p$。
证明：设 $r$ 为 $p$ 的缩系，则 $ar_i$ 也构成 $p$ 的缩系，于是，
$$\prod r_i \equiv \prod ar_i \pmod p$$
$$a^{\varphi(p)} \equiv 1 \pmod p$$
- $\gcd(a,b)=1$，$\varphi(ab)=\varphi(a)\varphi(b)$，即欧拉函数为积性函数。
证明：参见[数论基础](https://www.luogu.com.cn/article/v4svvb7w)中剩余系的复合。
- $n=\sum_{d|n}\varphi(d)$。
证明:设 $f(x)$ 为 $\gcd(k,n)=x,k<n$ 的 $k$ 个数。
有 $f(x)=\varphi(\frac{n}{x})$。
$$n=\sum_{i=1}^nf(i)$$
$$n=\sum_{d|n} \varphi(\frac{n}{d})=\sum_{d|n} \varphi(d)$$
- 若 $p \in P$，$\varphi(p^k)=p^k-p^{k-1}$。
证明：一共 $p^k$ 个数，不与 $p^k$ 互质的即 $p$ 的倍数有 $p^{k-1}$ 个。
- $\varphi(n)=n\prod_{p \in P,p \mid n}(1-\frac{1}{p})$。
证明：考虑唯一分解，
$$n=\prod_{p_i\in P,p_i \mid n}p_i^{k_i}$$
$$\varphi(n)=\prod \varphi(p_i^{k_i})$$
$$=\prod p_i^{k_i}(1-\frac{1}{p_i})$$
$$=n\prod_{p \in P,p|n}(1-\frac{1}{p})$$
- 任意 $m,n$，$\varphi(mn)\varphi(\gcd(m,n))=\varphi(m)\varphi(n)\gcd(m,n)$。
证明：用上一个结论展开计算即可。
## $\varphi(n)$ 的计算
### 计算一个 $\varphi(n)
用倒数第二个性质，考虑质因数分解然后计算，复杂度 O(\sqrt{n})，可以用 pollard_rho 优化质因数分解，复杂度 O(n^{\frac{1}{4}})。
inline int phi(int n){
int ans=n;
for(rg int p=2;p<=sqrt(n);p++){
if(n%p==0){
ans=ans/p*(p-1);
while(n%p==0) n/=p;
}
}
if(n>1) ans=ans/n*(n-1);//考虑n是素数的情况
return ans;
}
计算 1~n 所有 \varphi(i)
考虑线性筛，首先我们知道每个合数被其最小素因子筛去。
令 n=n'p，p 为 n 的最小素因子，那么 n 会被 p 和 n' 筛去。
若 p \mid n'，那么 n 和 n' 的素因子是一样的，所以根据倒数第二个性质，有 \varphi(n)=p\varphi(n')。
否则，有 \gcd(p,n')=1，\varphi(n)=\varphi(p)\varphi(n')。
inline void getphi(){
phi[1]=1;
for(rg int i=2;i<N;i++){
if(!vis[i]){
vis[i]=i;
prime[++cnt]=i;
phi[i]=i-1;
}
for(rg int j=1;j<=cnt;j++){
if(i*prime[j]>N) break;
vis[i*prime[j]]=prime[j];
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
例题
欧拉函数的应用
考虑以下性质，
\gcd(a,b)=\sum_{d|\gcd(a,b)} \varphi(d)
=\sum_d[d|a][d|b]\varphi(d)
可以用于 \gcd 的求和。
例 1
P2303
\sum_{i=1}^n \gcd(i,n)
=\sum_{i=1}^n \sum_d [d|i][d|n] \varphi(d)
=\sum_{d|n} \lfloor \frac{n}{d} \rfloor \varphi(d)
时间复杂度 O(d(n)\sqrt{n})。
例 2
P2398
\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)
=\sum_{i=1}^n \sum_{j=1}^n \sum_d [d|i][d|j] \varphi(d)
=\sum_{d=1}^n \lfloor \frac{n}{d} \rfloor^2 \varphi(d)
时间复杂度 O(n \sqrt {n})。
狄利克雷卷积
定义
给定数论函数 f,g，记 h(n)=\sum_{ij=n} f(i)g(j) 为两个函数的狄利克雷卷积，记为 h=f*g。
性质
若 f,g 为积性函数，则 f*g 也为积性函数。
证明：
考虑展开，若
h(ab)=h(a)h(b),\gcd(a,b)=1
则
\sum_{d|ab}f(d)g(\frac{ab}{d})
=\sum_{d_1|a}f(d_1)g(\frac{a}{d_1}) \sum_{d_2|b}f(d_2)g(\frac{b}{d_2})
由于 \gcd(a,b)=1，所以 \gcd(d_1,d_2)=1，于是 d_1d_2 取遍 ab 所有因子。
原式可化为，
\sum_{d_1d_2|ab}f(d_1)f(d_2)g(\frac{a}{d_1})g(\frac{b}{d_2})
根据积性函数性质可证。
根据欧拉函数的结论，有 \varphi * 1=id
狄利克雷卷积满足交换律，结合律与分配律。
设 \epsilon(n) 为狄利克雷卷积意义下的单位元函数，即 f* \epsilon =f ，易得 \epsilon(n)=[n=1]。
莫比乌斯函数
定义
给定数论函数 f，F=f*1，称 F 为 f 的和函数，展开为 F(n)=\sum_{d|n}f(n)。
已知 f 的情况下，求 F 是很简单的，但是反过来呢？
譬如说以下式子：
F(1)=f(1)
F(2)=f(1)+f(2)
F(3)=f(1)+f(3)
F(4)=f(1)+f(2)+f(4)
F(5)=f(1)+f(5)
F(6)=f(1)+f(2)+f(3)+f(6)
通过解方程组可以得到：
f(1)=F(1)
f(2)=F(2)-F(1)
f(3)=F(3)-F(1)
f(4)=F(4)-F(2)
f(5)=F(5)-F(1)
f(6)=F(6)-F(2)-F(3)+F(1)
发现其实反过来也是个狄利克雷卷积的形式，暂且把每一项的系数记为 \mu(i)，有
f=F*\mu
称这个 \mu 为莫比乌斯函数，可以观察到 \mu 为狄利克雷卷积意义下 1 的逆元，于是有 \mu * 1=\epsilon，这个结论也可用二项式定理证明，同时也证明了 \mu 是积性函数，有 \mu(1)=1。
考虑更一般性的定义，根据观察我们发现上面的式子里 f(4)=F(4)-F(2)，即 F(1) 的系数 \mu(4) 为 0，这是因为 \exist2,2^2|4，其他情况下根据容斥可以得出 \mu(n)=(-1)^{\omega(n)}。
于是我们得出了 \mu(n) 的更一般性定义：
\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}
性质
\mu$ 为积性函数，$\mu *1=\epsilon
根据定义，若 f=g*1，则 g=f*\mu，称这个定理为莫比乌斯反演。
由于 \varphi * 1=id，可得 \varphi =id *\mu。
由此可以得出衍生结论：
\sum_{d|n} \frac{\mu(d)}{d}=\frac{\varphi(n)}{n}
\mu(i) 的求法
显然又是我们的线性筛：D。
一般地，积性函数大部分都可以用线性筛递推求得。
inline void getmu(){
mu[1]=vis[1]=1;
for(rg int i=2;i<N;i++){
if(!vis[i]){
vis[i]=i;
prime[++cnt]=i;
mu[i]=-1;
}
for(rg int j=1;j<=cnt;j++){
if(i*prime[j]>N) break;
vis[i*prime[j]]=prime[j];
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
}
应用
例 1
求：
\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=1]
注意到 \epsilon(\gcd(i,j))=[\gcd(i,j)=1]，根据莫反 \epsilon=\mu * 1，于是，
\sum_{i=1}^n \sum_{j=1}^m \epsilon(\gcd(i,j))
=\sum_{i=1}^n\sum_{j=1}^m \sum_d [d|i][d|j] \mu(d)
=\sum_{d=1} \mu(d) \sum_{i=1}^n [d|i] \sum_{j=1}^m [d|j]
=\sum_{d=1}^{\min(n,m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor
然后就可以用整除分块来做，一次查询复杂度 O(\sqrt n)，预处理是 O(n) 的。
注意我们要记录 \mu 的前缀和，而这可以用杜教筛更快实现，当然就这种 O(n) 预处理的数据范围也不用小题大做对吧。
例 2
P1829
求：
\sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i,j)
显然，
=\sum_{i=1}^n \sum_{j=1}^m \frac{ij}{\gcd(i,j)}
考虑去枚举 \gcd(i,j)，
\sum_{i=1}^n \sum_{j=1}^m \sum_{d=1} [\gcd(i,j)=d]\frac{ij}{d}
考虑枚举 \frac{i}{d},\frac{j}{d}，
=\sum_{d=1}^{\min(n,m)} d \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j)=1]ij
令 f(n,m)=\sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i,j)=1]ij，
考虑莫反，
f(n,m)=\sum_{i=1}^n \sum_{j=1}^m \sum_{d=1} [d|i][d|j] \mu(d) ij
=\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{i=1}^n [d|i] i \sum_{j=1}^m [d|j] j
考虑枚举 \frac{i}{d},\frac{j}{d}，
=\sum_{d=1}^{\min(n,m)} d^2 \mu(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} j
再令 g(n,m)=\sum_{i=1}^{n} i \sum_{j=1}^{m} j，
显然，g(n,m)=\frac{nm(n+1)(m+1)}{4}，是 O(1) 的。
f(n,m)=\sum_{d=1}^{\min(n,m)} d^2 \mu(d) g(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)
可以整除分块对吧，但是预处理的是 d^2 \mu(d) 的前缀和，O(n) 处理即可。
再把 f(n,m) 代回去，
ans=\sum_{d=1}^{\min(n,m)}d f(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)
再来一次整除分块，是个等差数列求和，不用前缀和了。
总时间复杂度 O(n^{\frac{3}{4}})，证明如下：
整除分块套整除分块，总时间复杂度为，
T(n)=\sum_{i=2}^{\sqrt n} O(\sqrt {\frac{n}{i}})=O(\int_0^{\sqrt n} \sqrt \frac{n}{x} \mathrm dx)
=O(n^{\frac{3}{4}})