引言
在数论问题中,积性函数有着广泛的应用。 如在莫比乌斯反演问题中,函数变换之后如何快速维护前缀和往往是最重要也是最难的一步。如果维护的函数具有积性,那就可以尝试利用线性筛在$O(n)$的时限内完成预处理,从而达到优化复杂度的神奇作用。 本文的大部分相关性质及公式来自: $《线性筛与积性函数》- 贾志鹏$ 博主将试着证明其中的性质公式,严谨性可能欠缺,其目的主要是帮助记忆和理解。 因水平有限 若有错误之处还望指出qwq~
积性函数的定义和性质
定义: 对于一个定义域为$N^{+}$的函数$f$,对于任意两个互质的正整数$a,b$,均满足$f(ab)=f(a)f(b)$,则称函数$f$为积性函数 若对于任意整数$a,b$都有$f(ab) = f(a)f(b)$,则函数$f$被称为完全积性函数。
性质: (1)对于任意积性函数$f$,均有$f(1) = 1$
证明:因$1$与任何数都互质,假设存在一个正整数$a$满足$f(a)!=0$,故由定义:$$f(a) = f(1*a) = f(1)f(a)$$ 因$f(a)$不为$0$,故等号两端同时消去一个$f(a)$,得: $$f(1) = 1 $$ 证毕。
(2)对于一个大于$1$的正整数N,设$N = \prod p_i^{a_i}$,$p_i$为互不相同的素数。那么对于一个积性函数$f$来说,有: $$f(N) = f(\prod p_i^{a_i}) = \prod f(p_i^{a_i})$$ 若$f$完全积性,则$$f(N) = \prod f(p_i)^{a_i}$$
证明:由积性和完全积性的定义易得。
欧拉函数$\varphi$
定义:对于正整数$n$,$\varphi(n)$是小于n的正整数中与n互质的个数。
定义式:若’$n = \prod p_i^{a_i}$’ $$\varphi(n) = n \prod(1 - \frac{1}{p_i})$$
性质: (1)欧拉函数为积性函数,而不是完全积性函数。
证明:设两个互质的正整数$n,m$ 则:
$\varphi(n) = n \prod(1 - \frac{1}{p_i})$
$\varphi(m) =m \prod(1 - \frac{1}{p’_i})$
$\varphi(n)\varphi(m) = n \prod(1 - \frac{1}{p_i})m \prod(1 - \frac{1}{p’_i}) = nm\prod(1 - \frac{1}{p_i})(1 - \frac{1}{p’_i})$
因$n,m$互质,故 $p_i,p’_i$ 各不相同,且均为$nm$的质因子。
故推出: $\varphi(nm) = \varphi(n)\varphi(m)$ 积性函数性质得证。 而完全积性由上证明可见,$n,m$互质是一个严格且不可或缺的条件,可见,欧拉函数不是完全积性函数。
(2)假设存在一个素数$p$和一个正整数$k$,则:$\varphi(p^k) = p^k - p^{k-1}$
证明:
可以从反面来思考这件事,在小于$p^k$且与其不互质的数有以下形式:
$ p*1,p*2,…p * ( p^{k-1} - 1) $ (因为p是唯一的质因子)
故由定义:$\varphi(p^k) = $总数 - 不互质的数 = $(p^k-1) - (p^{k-1} -1) = p^k - p^{k-1}$ 证毕。
另外还可以从定义式出发去理解这个结论。 $$\varphi(p^k) = p^k(1-\frac{1}{p}) = p^k - p^{k-1}$$
(3)欧拉定理:若有互质的两个正整数$a,n$,则有$a^{\varphi(n)} \equiv 1(mod \ n)$ 此定理常用来求解逆元。
证明:(可参考百度百科)
(4)假设存在一个正整数n,则:$\sum_{d|n} \varphi(d) = n$
证明: 先考虑特殊情况: $n = 1$时 $\varphi(1) = 1$ 显然成立
对于一般情况,$n$一定可以质因数分解为:
$n = p_1^{a_1}p_2^{a_2}…p_k^{a_k}$
当n只含一个质因子时,即$n = p^a$
有:
$$ \sum_{d|n}\varphi(d) = \sum_{i = 0}^a \varphi (p^i) = 1 + \sum_{i=1}^{a}( p^i - p^{i-1}) = 1 + \sum_{i=1}^a(-p^{i-1} + p^i)$$
显然,将求和式展开,会有一些项可以合并。
比如$a = 3$时,原式等于: $$1 - p^0 + p^1- p^1 + p^2 - p^2 + p^3 = p^3 $$
可见:
$$\sum_{d|n}\varphi(d) = \sum_{i=0}^a \varphi(p^i) = p^a = n$$
当$n$含多个质因子时,即
$n = p_1^{a_1}p_2^{a_2}…p_k^{a_k}$
利用积性函数的性质有:
$$\sum_{d|n}\varphi(d) = \sum_{i=0}^{a_1} \varphi(p_1^i)\sum_{i=0}^{a_2} \phi(p_2^i) …… \sum_{i=0}^{a_k} \varphi(p_k^i)$$
同上易得: $$原式=p_1^{a_1}p_2^{a_2} …… p_k^{a_k} = n$$ 证毕。
(5)当$n>1$,小于$n$且与$n$互质的数之和为$$sum = \frac{n\varphi(n)}{2}$$
证明:在数论求$gcd$中,有两个非常出名的公式,基于这两个公式,出现了两种快速求$gcd$的方法,更相减损法和辗转相除法。这两个公式是:(假设有两个正整数$a,b$且满足 $a>b$) $gcd(a,b) = gcd(a,a-b)$ 和 $gcd(a,b) = gcd(b,a\%b)$
由第一个公式,知: 若$m$与$n$互质,则$n-m$也一定与$n$互质。 这样就能将保证当$n>2$时,$\varphi(n)$一定为偶数,且可两两配对,每一对的和都是$n$。 故$$sum = n\frac{\varphi(n)}{2} $$ 当$n=2$时,代入验证知,此公式依然满足。
证毕。
例题:HDU 3501 题意:求小于n且与n不互质的数之和。 思路:直接利用公式求反面,总数 - 反面数即为答案。 代码:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int A = 1e5 + 10;
bool vis[A];
int pri[A],tot;
void init(){
tot = 0;
vis[0] = vis[1] = 1;
for(int i=2 ;i<A ;i++){
if(vis[i] == 0) pri[++tot] = i;
for(int j=1 ;j<=tot&&pri[j]*i<A ;j++){
vis[pri[j]*i] = 1;
if(i%pri[j] == 0) break;
}
}
}
int main(){
init();
ll n;
while(~scanf("%I64d",&n) && n){
ll ans = (n*(n-1)/2)%mod;
ll res = n,m = n;
for(int i=1 ;i<=tot&&pri[i]*pri[i]<=n ;i++){
if(n%pri[i] == 0){
res = res/pri[i]*(pri[i]-1);
while(n%pri[i] == 0) n/=pri[i];
}
}
if(n!=1) res = res/n*(n-1);
ans = ans - res*m/2;
printf("%I64d\n",(ans%mod+mod)%mod);
}
return 0;
}
莫比乌斯函数$\mu$
定义式:
$$ \mu(n) = \begin{cases}
1 & (n=1)
(-1)^k&(n=p_1p_2…p_k)
0&(else)
\end{cases}$$
性质: (1)对于任意正整数n,有: $$\sum_{d|n} \mu(d) = [n == 1]$$
该性质在莫比乌斯反演中有着极大应用。
证明: 当$n = 1$时 等式显然成立。 当$n>1$时,令
$n = p_1^{a_1}p_2^{a_2}p_3^{a_3} … p_k^{a_k}$
考虑莫比乌斯函数取值的特殊性,若函数值不为$0$,则d只含每个质因子的$0$次或$1$次项。 故
$$\sum_{d|n}\mu(d) = C_k^0 - C_k^1 + C_k^2 …+(-1)^kC_k^k = \sum_{i=0}^k(-1)^iC_k^i$$
由二项式定理,原式等于:
$$\sum_{i=0}^k(-1)^iC_k^i = \sum_{i=0}^kC_k^i(-1)^i(1)^{k-i} = (-1 + 1)^k = 0$$
综上所述: 当$n=1$原式为$1$ 当$n>1$原式为$0$ 证毕。
(2)对于任意正整数$n$,有: $$\sum_{d|n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$
证明: 令$f(n)$满足:$f(n) = \sum_{d|n}\varphi(d)$
由欧拉函数的性质$(4)$:$f(n) = n$ 又由莫比乌斯反演:
$$\varphi(n) = \sum_{d|n}\mu(d)f(\frac{n}{d})$$
推出:
$$\varphi(n) = \sum_{d|n}n\frac{\mu(d)}{d} = n \sum_{d|n} \frac{\mu(d)}{d}$$
等式两边同除以n,得: $$\frac{\varphi(n)}{n} = \sum_{d|n}\frac{\mu(d)}{d} $$ 证毕。
线性筛求积性函数
欧拉函数$\varphi$
考虑将所有数分成三类: (1)质数 $\varphi(i) = i - 1$
(2)最小质因子指数为1:$\varphi(i*p) = \varphi(i) \varphi(p)$
(3)最小质因子指数大于1:$\varphi(i*p) = p*\varphi(i)$
(可从欧拉函数的定义式出发)
代码:
void init(){
tot = 0;phi[1] = 1;
for(int i=2 ;i<A ;i++){
if(!vis[i]){pri[++tot] = i;phi[i] = i-1;}
for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
vis[i*pri[j]] = 1;
if(i%pri[j] == 0){
phi[i*pri[j]] = pri[j] * phi[i];break;
}
phi[i*pri[j]] = phi[pri[j]] * phi[i];
}
}
}
莫比乌斯函数$\mu$
因为线性筛每次都是用最小质因子去筛每一个数。 故也可分为三类: (1)$i$为质数:$\mu[i] = -1$
(2)$i$已经包含最小质因子$p$:$\mu[i*p] = 0$
(3)$i$不包含最小质因子$p$ :$\mu[i*p] = -\mu[i]$
代码:
void init(){
tot = 0;mu[1] = 1;
for(int i=2 ;i<A ;i++){
if(!vis[i]){pri[++tot] = i;mu[i] = -1;}
for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
vis[i*pri[j]] = 1;
if(i%pri[j] == 0){mu[i*pri[j]] = 0;break;}
mu[i*pri[j]] = -mu[i];
}
}
}
以下为其他常见积性函数的线性筛:
约数个数函数$d$
仍然分三类讨论,此时我们还需要维护每一个数$i$最小质因子的指数$cnt[i]$
(1)$i$为质数:
$d[i] = 2 $
$cnt[i] = 1$
(2)$i$已经包含最小质因子$p$:
$d[i*p] = d[i]/(cnt[i]+1)*(cnt[i]+2) $ (由约数个数公式易得)
$cnt[i*p] = cnt[i] + 1$
(3)$i$不包含最小质因子$p$ :
$d[i*p] = d[i]*(cnt[p] + 1) = d[i]*2 $
$ cnt[i*p] = 1$
代码:
void init(){
tot = 0;d[1] = 1;
for(int i=2 ;i<A ;i++){
if(!vis[i]){pri[++tot] = i;d[i] = 2;cnt[i] = 1;}
for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
vis[i*pri[j]] = 1;
if(i%pri[j] == 0){
d[i*pri[j]] = d[i]/(cnt[i]+1)*(cnt[i]+2);
cnt[i*pri[j]] = cnt[i] + 1;
break;
}
d[i*pri[j]] = d[i]<<1;
cnt[i*pri[j]] = 1;
}
}
}
约数和函数$\sigma$
假设一个正整数$n$分解质因子之后为:
$n = p_1^{a_1}p_2^{a_2}p_3^{a_3} … p_k^{a_k}$
则
$$\sigma(n) = \sum_{i = 0}^{a_1}p_1^i \sum_{i=0}^{a_2}p_2^i….. \sum_{i=0}^{a_k}p_k^i$$
假设最小质因子为$p_1$
故线性筛中每一个被筛到的数比起原来的数,差别只在于:
$\sum_{i=0}^{a_1} p_1^i$
故我们可以维护两个量:
$sum[i]:i$的最小质因子$p_1$贡献的和:$\sum_{i=0}^{a_1} p_1^i$
$Mx[i]:$ $p_1^{a_1}$ $a_1$ 为最小质因子的最高次数。
然后又可以把所有数分成三类:
(1)$i$为质数:
$\sigma[i] = i+1 $ $sum[i] = i+1$ $Mx[i] = i$
(2)$i$已经包含最小质因子$p$:
$\sigma[i*p] = \sigma[i]/sum[i]*(sum[i]+Mx[i]*p) $
$sum[i*p] = sum[i] + Mx[i]*p$
$Mx[i*p] = Mx[i]*p$
(3)$i$不包含最小质因子$p$ :
$\sigma[i*p] = \sigma[i]*\sigma[p]= \sigma[i]*(p+1) $
$ sum[i*p] = p+1$
$Mx[i*p] = p$
代码:
void init(){
tot = 0;Sigma[1] = 1;
for(int i=2 ;i<A ;i++){
if(!vis[i]){
pri[++tot] = i;
Sigma[i] = 1 + i;
sum[i] = 1 + i;
Mx[i] = i;
}
for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
vis[i*pri[j]] = 1;
if(i%pri[j] == 0){
Sigma[i*pri[j]] = Sigma[i]/sum[i]*(sum[i] + Mx[i]*pri[j]);
sum[i*pri[j]] = sum[i] + Mx[i]*pri[j];
Mx[i*pri[j]] = Mx[i]*pri[j];
break;
}
Sigma[i*pri[j]] = Sigma[i]*(pri[j] + 1);
sum[i*pri[j]] = pri[j] + 1;
Mx[i*pri[j]] = pri[j];
}
}
}