数论基础知识（进阶篇） ACM

这是我在ACM竞赛中学习数论时整理的一些基础的知识点，这篇博客主要讨论数论中出现的一些数论函数和相关的一些算法。如果在理解上有所困难，请看数论基础知识（基础篇）

文章目录

算术基本定理
再谈gcd与lcm
积性函数
狄利克雷巻积
积性函数线性筛
莫比乌斯反演定理
莫比乌斯函数与欧拉函数之间关系

算术基本定理又称整数的唯一分解定理。

内容：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积（摘自于百度百科）。符号表示 n = p 1 c 1 ? p 2 c 2 ? . . . ? p m c m n=p_{1}^{c_{1}}*p_{2}^{c_{2}}*...*p_{m}^{c_{m}} n=p1c1???p2c2???...?pmcm??，其中 p 1 < p 2 < . . . < p m p_{1}p1?

算术基本定理是初等数论中一个基本的定理，也是许多其他定理的逻辑支撑点和出发点。
再谈gcd与lcm 正整数a, b,根据算术基本定理，a,b可以分别表示为：
a = p 1 α a 1 p 2 α a 2 . . . p m α a m a=p_{1}^{\alpha_{a_{1}}}p_{2}^{\alpha_{a_{2}}}...p_{m}^{\alpha_{a_{m}}} a=p1αa1???p2αa2???...pmαam???
b = p 1 α b 1 p 2 α b 2 . . . p m α b m b=p_{1}^{\alpha_{b_{1}}}p_{2}^{\alpha_{b_{2}}}...p_{m}^{\alpha_{b_{m}}} b=p1αb1???p2αb2???...pmαbm???
g c d ( a , b ) gcd(a,b) gcd(a,b)的本质就是：
g c d ( a , b ) = p 1 m i n { α a 1 , α b 1 } p 2 m i n { α a 2 , α b 2 } . . . p m m i n { α a m , α b m } gcd(a,b)=p_{1}^{min\{\alpha_{a_{1}},\alpha_{b_{1}}\}}p_2^{min\{\alpha_{a_{2}},\alpha_{b_{2}}\}}...p_{m}^{min\{\alpha_{a_{m}},\alpha_{b_{m}}\}} gcd(a,b)=p1min{αa1??,αb1??}?p2min{αa2??,αb2??}?...pmmin{αam??,αbm??}?
l c m ( a , b ) lcm(a,b) lcm(a,b)的本质就是：
l c m ( a , b ) = p 1 m a x { α a 1 , α b 1 } p 2 m a x { α a 2 , α b 2 } . . . p m m a x { α a m , α b m } lcm(a,b)=p_{1}^{max\{\alpha_{a_{1}},\alpha_{b_{1}}\}}p_2^{max\{\alpha_{a_{2}},\alpha_{b_{2}}\}}...p_{m}^{max\{\alpha_{a_{m}},\alpha_{b_{m}}\}} lcm(a,b)=p1max{αa1??,αb1??}?p2max{αa2??,αb2??}?...pmmax{αam??,αbm??}?
因此 a b = l c m ( a , b ) ? g c d ( a , b ) ab=lcm(a,b)*gcd(a,b) ab=lcm(a,b)?gcd(a,b)
积性函数假设正整数表示为： n = p 1 α 1 p 2 α 2 . . . p m α m n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{m}^{\alpha_{m}} n=p1α1??p2α2??...pmαm??

定义：当a,b互质时，有 f ( a ? b ) = f ( a ) ? f ( b ) f(a*b)=f(a)*f(b) f(a?b)=f(a)?f(b)则称函数f为积性函数。
当a,b时任意正整数时，有 f ( a ? b ) = f ( a ) ? f ( b ) f(a*b)=f(a)*f(b) f(a?b)=f(a)?f(b)则称函数f为完全积性函数。
根据定义可知，所有的积性函数满足 f ( 1 ) = 1 f(1)=1 f(1)=1
常见积性函数
- 欧拉函数
  - 【数论基础知识（进阶篇）】定义： 1~n 中与 n 互质的数的个数被称为欧拉函数，记为 φ ( N ) \varphi(N) φ(N)。
  - 计算公式： φ ( n ) = n ? p 1 ? 1 p 1 ? p 2 ? 1 p 2 ? . . . ? p m ? 1 p m \varphi(n)=n*\frac{p_{1}-1}{p_{1}}*\frac{p_{2}-1}{p_{2}}*...*\frac{p_{m}-1}{p_{m}} φ(n)=n?p1?p1??1??p2?p2??1??...?pm?pm??1?
  - 性质：
    - 1. 任意n>1,1~n中与n互质的数的和为 n ? φ ( n ) 2 \frac{n*\varphi(n)}{2} 2n?φ(n)?
      - 证明：若a与n互质，即 g c d ( a , n ) = g c d ( n ? a , n ) = 1 gcd(a,n)=gcd(n-a,n)=1 gcd(a,n)=gcd(n?a,n)=1,则n-a也与n互质，所以满足 n ? φ ( n ) 2 \frac{n*\varphi(n)}{2} 2n?φ(n)?
    - 2. ∑ d ∣ n φ ( d ) = n \sum_{d\mid n}\varphi(d)=n ∑d∣n?φ(d)=n
      - 证明：当 n = p α n=p^{\alpha} n=pα时， ∑ d ∣ n φ ( d ) = φ ( 1 ) + φ ( p ) + φ ( p 2 ) + . . . + φ ( p α ) = 1 + ( p ? 1 ) + p ( p ? 1 ) + . . . + p α ? 1 ( p ? 1 ) = p α = n \sum_{d\mid n}\varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^{2})+...+\varphi(p^{\alpha})=1+(p-1)+p(p-1)+...+p^{\alpha-1}(p-1)=p^{\alpha}=n ∑d∣n?φ(d)=φ(1)+φ(p)+φ(p2)+...+φ(pα)=1+(p?1)+p(p?1)+...+pα?1(p?1)=pα=n，令 f ( n ) = ∑ d ∣ n φ ( d ) f(n)=\sum_{d\mid n}\varphi(d) f(n)=∑d∣n?φ(d),因为 φ ( n ) \varphi(n) φ(n)是积性函数，所以 f ( n ) f(n) f(n)也为积性函数，将正整数n分解为n = p 1 α 1 p 2 α 2 . . . p m α m n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{m}^{\alpha_{m}} n=p1α1??p2α2??...pmαm??，则 f ( n ) = f ( p 1 α 1 ) ? f ( p 2 α 2 ) ? . . . ? f ( p m α m ) = p 1 α 1 p 2 α 2 . . . p m α m = n f(n)=f(p_{1}^{\alpha_{1}})*f(p_{2}^{\alpha_{2}})*...*f(p_{m}^{\alpha_{m}})=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{m}^{\alpha_{m}}=n f(n)=f(p1α1??)?f(p2α2??)?...?f(pmαm??)=p1α1??p2α2??...pmαm??=n
    - 3. 当n为质数时， φ ( n ) = n ? 1 \varphi(n)=n-1 φ(n)=n?1
      - 证明：显然n为质数时，与其互质的数的个数为n-1。
  - 求解方法：
    - 1. 根据计算公式直接计算，时间复杂度 O n O\sqrt{n} On ?
      代码实现：
      int eluer(int n) { int ans = n; for(int i = 2; i * i <= n; i ++){ if(n % i == 0) { ans = (ans / i) * (i - 1); while(n % i == 0) n /= i; } } if(n > 1) ans = (ans / n) * (n - 1); return ans; }
    - 2. 线性筛法， O N O\sqrt{N} ON ?复杂度内求解1～n所有的欧拉函数
      - 当 p ∣ n 且 p 2 ∣ n , 则 φ ( n ) = φ ( n p ) ? p p\mid n且p^{2}\mid n,则\varphi(n)=\varphi(\frac{n}{p})*p p∣n且p2∣n,则φ(n)=φ(pn?)?p;
      - 当 p ∣ n 且 p 2 ? n , 则 φ ( n ) = φ ( n p ) ? φ ( p ) p\mid n且p^{2}\nmid n,则\varphi(n)=\varphi(\frac{n}{p})*\varphi(p) p∣n且p2?n,则φ(n)=φ(pn?)?φ(p)
        代码实现：
      int maxn = 1e6 + 100; bool v[maxn]; int phi[maxn], p[maxn]; void sieze(int n) { int m = 0; memset(v, false, sizeof(v)); for(int i = 2; i <= n; i ++){ if(!v[i]){ p[++ m] = i; phi[i] = i-1; } for(int j = 1; j <= m && i * p[j] <= n; j ++){ v[i * p[j]] = true; if(i % p[j]) phi[i * p[j]] = phi[i] * p[j]; else { phi[i * p[j]] = phi[i] * phi[p[j]]; break; } } } }
  - 莫比乌斯函数
    - 定义：μ ( n ) = { 0 , ? i ∈ [ 1 , m ] , c i > 1 1 , m ≡ 0 ( m o d2 ) , ? i ∈ [ 1 , m ] , c i = 1 ? 1 , m ≡ 1 ( m o d2 ) , ? i ∈ [ 1 , m ] , c i = 1 \mu(n)=\Bigg\{ \begin{array}{ccc} 0, \exists i\in[1,m],c_{i}>1\\ 1, m\equiv0(mod\ 2),\forall i\in[1,m],c_{i}=1 \\ -1, m\equiv1(mod\ 2),\forall i\in[1,m],c_{i}=1\\ \end{array} μ(n)={0,?i∈[1,m],ci?>11,m≡0(mod 2),?i∈[1,m],ci?=1?1,m≡1(mod 2),?i∈[1,m],ci?=1?
    通俗的说，对于n如果存在平方因子，则 μ ( n ) = 0 \mu(n)=0 μ(n)=0,若不存在平方因子，n的质因数的个数为m，则 μ ( n ) = ( ? 1 ) m \mu(n)=(-1)^{m} μ(n)=(?1)m。
    - 求解方法：
      51Nod1240莫比乌斯函数
      - 1.直接求法： O n O\sqrt{n} On ?求解一个数
        的 μ ( n ) \mu(n) μ(n)
        代码实现：
      int mu(int n) { int m = 0; for(int i = 2; i * i <= n; i ++){ if(n % i == 0){ int cnt = 0; m ++; while(n % i == 0){ cnt ++; n /= i; if(cnt >= 2) return 0; } } } if(n > 1) m ++; return m % 2 == 0 ? 1 : -1; }
      - O ( n ) O(n) O(n)求解1～n以内的所有 μ ( n ) \mu(n) μ(n)
      const int maxn = 1e5 + 10; bool v[maxn]; int mu[maxn], p[maxn]; void sieze(int n) { int m = 0; memset(v, false, sizeof(v)); mu[1] = 1; for(int i = 2; i <= n; i ++){ if(!v[i]){ p[++ m] = i; mu[i] = -1; } for(int j = 1; j <= m && i * p[j] <= n; j ++){ v[i * p[j]] = true; if(i % p[j]) { mu[i * p[j]] = -mu[i]; } else { mu[i * p[j]] = 0; break; } } } }
- 约数个数函数
  - 定义：表示正整数n的所有约数的个数，记为 d ( n ) d(n) d(n) ，也记作 τ ( n ) \tau(n) τ(n)。
  - 计算公式： d ( n ) = ( α 1 + 1 ) ? ( α 2 + 1 ) ? . . . ? ( α m + 1 ) = Π i = 1 m ( α i + 1 ) d(n)=(\alpha_{1}+1)*(\alpha_{2}+1)*...*(\alpha_{m}+1)=\Pi_{i=1}^{m}(\alpha_{i}+1) d(n)=(α1?+1)?(α2?+1)?...?(αm?+1)=Πi=1m?(αi?+1)。
  - 求解方法：
    - 1. O n O\sqrt{n} On ?求解一个数 d ( n ) d(n) d(n)
      代码实现：
      int d(n) { int ans = 1; for(int i = 2; i * i <= n; i ++){ if(n % i == 0){ int cnt = 0; while(n % i == 0){ n /= i; cnt ++; } ans *= (cnt + 1); } } if(n > 1) ans *= 2; return ans; }
    - O ( n ) O(n) O(n)求解1~n以内所有的d(n)
      代码实现：
      const int maxn = 1e5 + 100; int p[maxn], num[maxn], d[maxn]; bool v[maxn]; int m = 0; void sieze(int n) { m = 0; memset(v, false, sizeof(v)); d[1] = 1; num[1] = 1; for(int i = 2; i <= n; i ++){ if(!v[i]){ p[++ m] = i; d[i] = 2; num[i] = 1; } for(int j = 1; j <= m && i * p[j] <= n; j ++){ v[i * p[j]] = true; if(i % p[j]){ d[i * p[j]] = d[i] * d[p[j]]; num[i * p[j]] = 1; } else { d[i * p[j]] = (d[i] / (num[i] + 1)) * (num[i] + 2); num[i * p[j]] = num[i] + 1; break; } } } }
- 约数和函数
  - 定义：表示正整数n的所有约数的和，记作 σ ( n ) \sigma(n) σ(n)
  - 计算公式： σ ( n ) = ( 1 + p 1 + p 1 2 + . . . + p 1 α 1 ) ( 1 + p 2 + p 2 2 + . . . + p 2 α 2 ) ? . . . ? ( 1 + p m + p m 2 + . . . + p m α m ) = p 1 α 1 + 1 ? 1 p 1 ? 1 ? p 2 α 2 + 1 ? 1 p 2 ? 1 ? . . . ? p m α m + 1 ? 1 p m ? 1 = Π i = 1 m p i α i + 1 ? 1 p i ? 1 \sigma(n)=(1+p_{1}+p_{1}^{2}+...+p_{1}^{\alpha_{1}})(1+p_{2}+p_{2}^{2}+...+p_{2}^{\alpha_{2}})*...*(1+p_{m}+p_{m}^{2}+...+p_{m}^{\alpha_{m}})=\frac{p1^{\alpha_{1}+1}-1}{p_{1}-1}*\frac{p_{2}^{\alpha_{2}+1}-1}{p_{2}-1}*...*\frac{p_{m}^{\alpha_{m}+1}-1}{p_{m}-1}=\Pi_{i=1}^{m}\frac{p_{i}^{\alpha_{i}+1}-1}{p_{i}-1} σ(n)=(1+p1?+p12?+...+p1α1??)(1+p2?+p22?+...+p2α2??)?...?(1+pm?+pm2?+...+pmαm??)=p1??1p1α1?+1?1??p2??1p2α2?+1??1??...?pm??1pmαm?+1??1?=Πi=1m?pi??1piαi?+1??1?
- 元函数
  - 定义：记作 ε ( n ) , ε ( n ) = [ n = 1 ] \varepsilon(n),\varepsilon(n)=[n=1] ε(n),ε(n)=[n=1]，当且仅当n为1时 ε ( n ) = 1 \varepsilon(n)=1 ε(n)=1，否则均为0。
- 恒等函数
  - 定义：记作 I ( n ) I(n) I(n),对于任意的n都是1，即 I ( n ) = 1 I(n)=1 I(n)=1
- 单位函数
  - 定义：记为 i d ( n ) , i d ( n ) = n id(n),id(n)=n id(n),id(n)=n

狄利克雷巻积

定义：两个数论函数f(n)和g(n)作巻积记为 ( f ? g ) ( n ) = ∑ d ∣ n f ( d ) ? g ( n d ) (f*g)(n)=\sum_{d\mid n}f(d)*g(\frac{n}{d}) (f?g)(n)=∑d∣n?f(d)?g(dn?)，简记为 f ? g f*g f?g
运算性质: 以下运算性质都可根据定义得到
- 1.交换律：f ? g = g ? f f*g=g*f f?g=g?f
- 2.结合律：( f ? g ) ? h = f ? ( g ? h ) (f*g)*h=f*(g*h) (f?g)?h=f?(g?h)
- 3.分配率：( f + g ) ? h = f ? h + g ? h (f+g)*h=f*h+g*h (f+g)?h=f?h+g?h
几个重要的巻积
- 1.f ? ε = f f*\varepsilon=f f?ε=f
  - 证明： f ? ε = ∑ d ∣ n f ( d ) ? ε ( n d ) = f ( n ) ? ε ( 1 ) = f ( n ) f*\varepsilon=\sum_{d\mid n}f(d)*\varepsilon(\frac{n}{d})=f(n)*\varepsilon(1)=f(n) f?ε=∑d∣n?f(d)?ε(dn?)=f(n)?ε(1)=f(n)
- 2.I ? μ = ε I*\mu=\varepsilon I?μ=ε
  - 证明：当n=1时， I ? μ = 1 I*\mu=1 I?μ=1,
    当n>1时，将n分解为 n = p 1 α 1 ? p 2 α 2 ? . . . ? p m α m n=p_{1}^{\alpha_{1}}*p_{2}^{\alpha_{2}}*...*p_{m}^{\alpha_{m}} n=p1α1???p2α2???...?pmαm??
    I ? μ = μ ? I = ∑ d ∣ n μ ( d ) ? I ( n d ) = ∑ d ∣ n μ ( d ) I*\mu =\mu*I=\sum_{d\mid n}\mu(d)*I(\frac{n}{d})=\sum_{d\mid n}\mu(d) I?μ=μ?I=∑d∣n?μ(d)?I(dn?)=∑d∣n?μ(d)根据莫比乌斯函数的定义，
    ∑ d ∣ n = ( C m 0 + C m 2 + C m 4 + . . . + C m ? m 2 ? ? 2 ) ? ( C m 1 + C m 3 + . . . + C m ( ? m ? 1 2 ? ? 2 ) + 1 ) = 0 \sum_{d\mid n}=(C_{m}^{0}+C_{m}^{2}+C_{m}^{4}+...+C_{m}^{\lfloor\frac{m}{2}\rfloor*2})-(C_{m}^{1}+C_{m}^{3}+...+C_{m}^{(\lfloor\frac{m-1}{2}\rfloor*2)+1})=0 ∑d∣n?=(Cm0?+Cm2?+Cm4?+...+Cm?2m???2?)?(Cm1?+Cm3?+...+Cm(?2m?1???2)+1?)=0
- 3.φ ? I = i d \varphi*I=id φ?I=id
  - 证明：φ ? I = ∑ d ∣ n φ ( n ) ? I ( n d ) = ∑ d ∣ n φ ( n ) = n \varphi*I=\sum_{d\mid n}\varphi(n)*I(\frac{n}{d})=\sum_{d\mid n}\varphi(n)=n φ?I=∑d∣n?φ(n)?I(dn?)=∑d∣n?φ(n)=n,根据欧拉函数的性质可得。
注：两个积性函数作巻积，结果仍然为积性函数

积性函数线性筛之前的欧拉函数、莫比乌斯函数、约数个数函数 O ( n ) O(n) O(n)计算1～n以内的所有的函数，就是积性函数线性筛的做法，原理基本相同。只要是积性函数，原则上都能线性筛出1~n以内的所有函数值。
以约数和个数为例,令 f ( n ) = σ ( n ) f(n)=\sigma(n) f(n)=σ(n)
当n是质数时， f ( n ) = n + 1 f(n)=n+1 f(n)=n+1
将正整数n分解成 n = p 1 α 1 p 2 α 2 . . . p m α m , 满足 p 1 < p 2 < . . . < p m n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{m}^{\alpha_{m}},满足p_{1}n=p1α1??p2α2??...pmαm??,满足p1? 定义 l o w [ n ] = p 1 α 1 low[n]=p_{1}^{\alpha_{1}} low[n]=p1α1??
当 p ∣ n 且 p 2 ? n p\mid n且p^{2}\nmid n p∣n且p2?n,则 p p p与 n p \frac{n}{p} pn?互质，则 d ( n ) = d ( n d ) ? d ( p ) d(n)=d(\frac{n}{d})*d(p) d(n)=d(dn?)?d(p)
当 p ∣ n 且 p 2 ∣ n p\mid n且p^{2}\mid n p∣n且p2∣n,若 l o w ( n p ) = n p , f ( n ) = f ( n p ) ? p + 1 low(\frac{n}{p})=\frac{n}{p},f(n)=f(\frac{n}{p})*p+1 low(pn?)=pn?,f(n)=f(pn?)?p+1,否则， n p l o w [ n p ] \frac{\frac{n}{p}}{low[\frac{n}{p}]} low[pn?]pn??与 l o w [ n p ] ? p low[\frac{n}{p}]*p low[pn?]?p互质，则 f ( n ) = f ( n p l o w [ n p ] ) ? f ( l o w [ n p ] ? p ) f(n)=f(\frac{\frac{n}{p}}{low[\frac{n}{p}]})*f(low[\frac{n}{p}]*p) f(n)=f(low[pn?]pn??)?f(low[pn?]?p)
代码实现：

const int maxn = 1e5 + 100; int p[maxn], low[maxn], f[maxn]; bool v[maxn]; int m = 0; void sieze(int n) { m = 0; memset(v, false, sizeof(v)); f[1] = 1; low[1] = 1; for(int i = 2; i <= n; i ++){ if(!v[i]){ p[++ m] = i; f[i] = i + 1; low[i] = i; } for(int j = 1; j <= m && i * p[j] <= n; j ++){ v[i * p[j]] = true; if(i % p[j]){ f[i * p[j]] = f[i] * f[p[j]]; low[i * p[j]] = p[j]; } else { if(low[i] == i) f[i * p[j]] = f[i] * p[j] + 1; else f[i * p[j]] = f[i / low[i]] * f[low[i] * p[j]]; low[i * p[j]] = low[i] * p[j]; break; } } } }

莫比乌斯反演定理

定理说明：若存在 F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum_{d\mid n}f(d) F(n)=∑d∣n?f(d)，则有 f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=\sum_{d\mid n}\mu(d)F(\frac{n}{d}) f(n)=∑d∣n?μ(d)F(dn?)
证明：F = f ? I ? F ? μ = f ? I ? μ = f ? ε = f F=f*I\Leftrightarrow F*\mu=f*I*\mu=f*\varepsilon=f F=f?I?F?μ=f?I?μ=f?ε=f
莫比乌斯反演例题
- BZOJ1011：题解

莫比乌斯函数与欧拉函数之间关系

φ ( n ) n = ∑ d ∣ n μ ( d ) d \frac{\varphi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d} nφ(n)?=∑d∣n?dμ(d)?
证明：根据 ∑ d ∣ n φ ( d ) = n \sum_{d\mid n}\varphi(d)=n ∑d∣n?φ(d)=n，则 i d = φ ? I ? i d ? μ = φ ? I ? μ = φ ? ε = φ id=\varphi*I\Leftrightarrow id*\mu=\varphi*I*\mu=\varphi*\varepsilon=\varphi id=φ?I?id?μ=φ?I?μ=φ?ε=φ，则 φ ( n ) = ∑ d ∣ n μ ( d ) ? n d ? φ ( n ) n = ∑ d ∣ n μ ( d ) d \varphi(n)=\sum_{d\mid n}\mu(d)*\frac{n}{d}\Leftrightarrow\frac{\varphi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d} φ(n)=∑d∣n?μ(d)?dn??nφ(n)?=∑d∣n?dμ(d)?。