你所热爱的,就是你的生活关于友链

数论学习入门 #1

swwind#数论

数论虽然在 NOIP 中不作深入的要求,但是在这之上的比赛就经常会有涉及到这类知识的算法题目。

本文来总结整理一下一些初等的数论知识。

Mathematics is the queen of the sciences—and number theory is the queen of mathematics. 数学是科学的皇后,数论是数学的皇后。

——卡尔·弗里德里希·高斯

基本定理和性质

本文所使用的符号均参照数学选修 4-6

质数与合数

在大于 11 的自然数中,除了 11 和该数自身外,无法被其他自然数整除的数称为质数(aka. 素数)。

大于 11 的自然数若不是素数,则称之为合数(aka. 合成数)。

11 既不是质数,也不是合数。

最大公约数和最小公倍数

最大公约数(abbr. gcd, greatest common divisor)指能够整除多个整数的最大正整数。

如果 ccaabb 的最大公约数,我们记为 (a,b)=c(a, b) = c

如果 (a,b)=1(a,b)=1,那么我们称 aabb 互质,可以记为 aba \bot b

最小公倍数(abbr. lcm, least common multiple)指能够被多个整数整除的最小正整数。

如果 ccaabb 的最大公约数,我们记为 [a,b]=c[a, b] = c

一个大家都知道的结论:(a,b)×[a,b]=ab(a, b) \times [a, b] = ab

整除

如果 aa 能够整除 bb,我们称 aabb约数因子,记为 aba \mid b

相反,如果 aa 不能够整除 bb,我们记为 aba \nmid b

整除有一些优秀的性质:

  • ab,bc,ababca \mid b, b \mid c, a \bot b \Rightarrow ab \mid c
  • abc,abaca \mid bc, a \bot b \Rightarrow a \mid c
  • abcaba \mid bc \Rightarrow a \mid baca \mid c

正确性显然。

Sum 和 Product

i=1nai=a1+a2+...+ani=1nai=a1a2...an\begin{aligned}
\sum_{i=1}^{n}a_i &= a_1 + a_2 + ... + a_n \\
\prod_{i=1}^{n}a_i &= a_1 a_2 ... a_n
\end{aligned}

算数基本定理

n>1n>1,则 nn 可以分解成素数的乘积

n=p1p2...pkn = p_1p_2...p_k

如果不计这些素数的次序,则分解式是唯一的。

n=p1a1p2a2...pkakn = p_1^{a_1}p_2^{a_2}...p_k^{a_k}nn 的标准分解式,若用 d(n)d(n) 表示 nn 的所有正约数的个数,那么

d(n)=i=1k(ai+1)d(n) = \prod_{i=1}^{k}(a_i+1)

组合数与阶乘

组合数(aka. 二项式系数(nm)\binom{n}{m} 表示从 nn 个本质不同的物品中选出 mm 个物品的方案数(不计选择的顺序)。

(nm)=n!(nm)!m!\binom{n}{m} = \frac{n!}{(n-m)!m!}

其中

n!={1,n=0i=1ni,n>0n!=\begin{cases}1,&n=0 \\
\prod_{i=1}^{n}i,&n>0
\end{cases}

于是我们有递推式:

(nm)=(n1m)+(n1m1)\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}

二项式定理

(x+y)n=i=0n(ni)xniyi(x+y)^n = \sum_{i=0}^{n}\binom{n}{i}x^{n-i}y^i

同余

如果 aabbpp 的余数相等,那么我们记为 ab(modp)a \equiv b \pmod p

数论函数

积性函数

如果 f(x)f(x) 是积性函数,那么对于 a,bN,ab\forall a, b \in N, a \bot b,满足 f(ab)=f(a)f(b)f(ab) = f(a)f(b)

下面是一些常见的积性函数:

  • σk(n)=dndk\sigma_k(n) = \sum_{d|n}d^k
  • d(n)=σ0(n)d(n)=\sigma_0(n) 表示 nn 的正因子个数
  • σ(n)=σ1(n)\sigma(n)=\sigma_1(n) 表示 nn 的所有正因子的和
  • idk(n)=nkid_k(n)=n^k
  • l(n)=id0(n)=1l(n)=id_0(n)=1
  • id(n)=id1(n)=nid(n)=id_1(n)=n
  • ε(n)={1,n=10,n>1\varepsilon(n)=\begin{cases}1,&n=1\\\\0,&n>1\end{cases}

欧拉函数

莱昂哈德·欧拉(1707-1783)

欧拉函数 φ(n)\varphi(n) 表示小于 nn 的与 nn 互质的正整数的个数。

n=p1a1p2a2...pkakn = p_1^{a_1}p_2^{a_2}...p_k^{a_k},则有

φ(n)=n(11p1)(11p2)...(11pk)\varphi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})

φ(n)\varphi(n)积性函数

欧拉定理:设 m>1m>1(a,m)=1(a,m)=1,则 aφ(m)1(modm)a^{\varphi(m)} \equiv 1 \pmod m

如果 mm 是质数,那么 φ(m)=m1\varphi(m)=m-1,这其实就是费马小定理了。

费马小定理:设 pp 是质数,(a,p)=1(a,p)=1,则 ap11(modp)a^{p-1} \equiv 1 \pmod p

扩展欧拉定理

ab{abmodφ(p),apab,b<φ(p)abmodφ(p)+φ(p),bφ(p)(modp)a^b \equiv \begin{cases}
a^{b \mod \varphi(p)}, &a \bot p \\
a^{b} , &b < \varphi(p) \\
a^{b \mod \varphi(p) + \varphi(p)}, &b \geq \varphi(p)
\end{cases} \pmod p
皮埃尔·德·费马(1601-1665)

例题:222...modp2^{2^{2^{...}}} \mod p

解:S=222...S = 2^{2^{2^{...}}}S2Smodφ(p)+φ(p)(modp)S \equiv 2^{S \mod \varphi(p) + \varphi(p)} \pmod p 于是问题可以转化为求 SSφ(p)\varphi(p) 取模的子问题。 以此类推,当模数为 11 时,答案显然为 00。 然后递归回去计算即可。

莫比乌斯函数

莫比乌斯函数 μ(n)\mu(n) 的定义:

n=p1a1p2a2...pkakn = p_1^{a_1}p_2^{a_2}...p_k^{a_k}

μ(n)={1,n=1(1)k,ai=10,ai>1\mu(n) = \begin{cases}
1, & n = 1 \\\\
(-1) ^ k, & \forall a_i=1 \\\\
0, & \exists a_i \gt 1
\end{cases}

μ(n)\mu(n) 也是积性函数。

dnμ(d)=ε(n)\sum_{d \mid n}\mu(d) = \varepsilon(n)

算法

狄利克雷卷积

约翰·彼得·古斯塔夫·勒热纳·狄利克雷(1805-1859)

如果 f(n),g(n)f(n),g(n) 是数论函数,令 h=f×gh = f \times g,则

h(n)=dnf(d)g(nd)h(n)=\sum_{d|n}f(d)g(\frac{n}{d})

狄利克雷卷积有一些优秀的性质:

  • 交换律 f×g=g×ff\times g=g\times f
  • 结合律 (f×g)×h=f×(g×h)(f\times g)\times h=f\times (g\times h)
  • 分配律 f×(g+h)=f×g+f×hf\times (g+h)=f\times g+f\times h
  • 单位元 ε×f=f\varepsilon\times f=f

一些公式:

  • d(n)=dnl(d)d=l×ld(n)=\sum_{d|n}l(d) \Leftrightarrow d = l \times l
  • σ(n)=dnid(d)σ=l×id\sigma(n)=\sum_{d|n}id(d) \Leftrightarrow \sigma = l \times id
  • ε(n)=dnμ(d)ε=l×μ\varepsilon(n)=\sum_{d|n}\mu(d) \Leftrightarrow \varepsilon = l \times \mu
  • φ(n)=dnμ(d)ndφ=μ×id\varphi(n)=\sum_{d|n}\mu(d)\frac nd \Leftrightarrow \varphi = \mu \times id
  • n=dnφ(d)id=l×φn=\sum_{d|n}\varphi(d) \Leftrightarrow id = l \times \varphi

莫比乌斯反演

如果 f(n),g(n)f(n),g(n) 是数论函数,则有

f(n)=dng(d)g(n)=dnμ(d)f(nd)f(n)=\sum_{d \mid n}g(d) \Leftrightarrow g(n) = \sum_{d \mid n}\mu(d)f(\frac{n}{d})

证明:

f=g×lf×μ=g×l×μf×μ=g×εf×μ=g\begin{aligned}
f &= g \times l \\
f \times \mu &= g \times l \times \mu \\
f \times \mu &= g \times \varepsilon \\
f \times \mu &= g
\end{aligned}

变形:

f(k)=d=1nkg(dk)g(k)=d=1nkμ(d)f(dk)f(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} g(dk) \Rightarrow g(k) = \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)f(dk)

这怎么证啊。。。

例题:(nm)(n \leq m)

i=1nj=1m[(i,j)=k]\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=k]

解:

f(k)=i=1nj=1m[(i,j)=k]g(k)=i=1nj=1m[k(i,j)]f(k)=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=k] \\
g(k)=\sum_{i=1}^{n}\sum_{j=1}^{m}[k \mid (i,j)]

则有

g(k)=d=1nkf(dk)g(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}f(dk)

根据莫比乌斯反演得

f(k)=d=1nkμ(d)g(dk)f(k) = \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)g(dk)

考虑如何计算 g(k)g(k),我们马上就能发现

g(k)=nkmkg(k) = \left\lfloor \frac{n}{k} \right\rfloor\left\lfloor \frac{m}{k} \right\rfloor

所以

f(k)=d=1nkμ(d)ndkmdkf(k) = \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)\left\lfloor \frac{n}{dk} \right\rfloor\left\lfloor \frac{m}{dk} \right\rfloor

直接计算是 O(n)O(n) 的,可以利用前缀和和分块的技巧优化到单次询问 O(n+m)O(\sqrt{n}+\sqrt{m})

总结

如果你不知道一个公式怎么证明,那就打表 打表找规律大法好

文章写太长不好,剩下来的以后讲。 下次应该会多写几道例题。

别问我为什么退役了才写这个