数论学习入门 #1
swwind#数论
数论虽然在 NOIP 中不作深入的要求,但是在这之上的比赛就经常会有涉及到这类知识的算法题目。
本文来总结整理一下一些初等的数论知识。
Mathematics is the queen of the sciences—and number theory is the queen of mathematics.
数学是科学的皇后,数论是数学的皇后。
——卡尔·弗里德里希·高斯
基本定理和性质
本文所使用的符号均参照数学选修 4-6
质数与合数
在大于 1
的自然数中,除了 1
和该数自身外,无法被其他自然数整除的数称为质数(aka. 素数)。
大于 1
的自然数若不是素数,则称之为合数(aka. 合成数)。
1
既不是质数,也不是合数。
最大公约数和最小公倍数
最大公约数(abbr. gcd, greatest common divisor)指能够整除多个整数的最大正整数。
如果 c
是 a
和 b
的最大公约数,我们记为 (a,b)=c
。
如果 (a,b)=1
,那么我们称 a
与 b
互质,可以记为 a⊥b
。
最小公倍数(abbr. lcm, least common multiple)指能够被多个整数整除的最小正整数。
如果 c
是 a
和 b
的最大公约数,我们记为 [a,b]=c
。
一个大家都知道的结论:(a,b)×[a,b]=ab
整除
如果 a
能够整除 b
,我们称 a
是 b
的约数或因子,记为 a∣b
。
相反,如果 a
不能够整除 b
,我们记为 a∤b
。
整除有一些优秀的性质:
a∣b,b∣c,a⊥b⇒ab∣c
a∣bc,a⊥b⇒a∣c
a∣bc⇒a∣b
或 a∣c
正确性显然。
Sum 和 Product
i=1∑naii=1∏nai=a1+a2+...+an=a1a2...an
算数基本定理
设 n>1
,则 n
可以分解成素数的乘积
n=p1p2...pk
如果不计这些素数的次序,则分解式是唯一的。
设 n=p1a1p2a2...pkak
是 n
的标准分解式,若用 d(n)
表示 n
的所有正约数的个数,那么
d(n)=i=1∏k(ai+1)
组合数与阶乘
组合数(aka. 二项式系数) (mn)
表示从 n
个本质不同的物品中选出 m
个物品的方案数(不计选择的顺序)。
(mn)=(n−m)!m!n!
其中
n!={1,∏i=1ni,n=0n>0
于是我们有递推式:
(mn)=(mn−1)+(m−1n−1)
二项式定理:
(x+y)n=i=0∑n(in)xn−iyi
同余
如果 a
和 b
对 p
的余数相等,那么我们记为 a≡b(modp)
数论函数
积性函数
如果 f(x)
是积性函数,那么对于 ∀a,b∈N,a⊥b
,满足 f(ab)=f(a)f(b)
。
下面是一些常见的积性函数:
σk(n)=∑d∣ndk
d(n)=σ0(n)
表示 n
的正因子个数
σ(n)=σ1(n)
表示 n
的所有正因子的和
idk(n)=nk
l(n)=id0(n)=1
id(n)=id1(n)=n
ε(n)=⎩⎨⎧1,0,n=1n>1
欧拉函数
欧拉函数 φ(n)
表示小于 n
的与 n
互质的正整数的个数。
设 n=p1a1p2a2...pkak
,则有
φ(n)=n(1−p11)(1−p21)...(1−pk1)
φ(n)
是积性函数。
欧拉定理:设 m>1
,(a,m)=1
,则 aφ(m)≡1(modm)
如果 m
是质数,那么 φ(m)=m−1
,这其实就是费马小定理了。
费马小定理:设 p
是质数,(a,p)=1
,则 ap−1≡1(modp)
扩展欧拉定理:
ab≡⎩⎨⎧abmodφ(p),ab,abmodφ(p)+φ(p),a⊥pb<φ(p)b≥φ(p)(modp)
例题: 求 222...modp
解: 令 S=222...
则 S≡2Smodφ(p)+φ(p)(modp)
于是问题可以转化为求 S
对 φ(p)
取模的子问题。
以此类推,当模数为 1
时,答案显然为 0
。
然后递归回去计算即可。
莫比乌斯函数
莫比乌斯函数 μ(n)
的定义:
设 n=p1a1p2a2...pkak
,
μ(n)=⎩⎨⎧1,(−1)k,0,n=1∀ai=1∃ai>1
μ(n)
也是积性函数。
d∣n∑μ(d)=ε(n)
算法
狄利克雷卷积
如果 f(n),g(n)
是数论函数,令 h=f×g
,则
h(n)=d∣n∑f(d)g(dn)
狄利克雷卷积有一些优秀的性质:
- 交换律
f×g=g×f
- 结合律
(f×g)×h=f×(g×h)
- 分配律
f×(g+h)=f×g+f×h
- 单位元
ε×f=f
一些公式:
d(n)=∑d∣nl(d)⇔d=l×l
σ(n)=∑d∣nid(d)⇔σ=l×id
ε(n)=∑d∣nμ(d)⇔ε=l×μ
φ(n)=∑d∣nμ(d)dn⇔φ=μ×id
n=∑d∣nφ(d)⇔id=l×φ
莫比乌斯反演
如果 f(n),g(n)
是数论函数,则有
f(n)=d∣n∑g(d)⇔g(n)=d∣n∑μ(d)f(dn)
证明:
ff×μf×μf×μ=g×l=g×l×μ=g×ε=g
变形:
f(k)=d=1∑⌊kn⌋g(dk)⇒g(k)=d=1∑⌊kn⌋μ(d)f(dk)
这怎么证啊。。。
例题:
求 (n≤m)
i=1∑nj=1∑m[(i,j)=k]
解:
设
f(k)=i=1∑nj=1∑m[(i,j)=k]g(k)=i=1∑nj=1∑m[k∣(i,j)]
则有
g(k)=d=1∑⌊kn⌋f(dk)
根据莫比乌斯反演得
f(k)=d=1∑⌊kn⌋μ(d)g(dk)
考虑如何计算 g(k)
,我们马上就能发现
g(k)=⌊kn⌋⌊km⌋
所以
f(k)=d=1∑⌊kn⌋μ(d)⌊dkn⌋⌊dkm⌋
直接计算是 O(n)
的,可以利用前缀和和分块的技巧优化到单次询问 O(n+m)
。
总结
如果你不知道一个公式怎么证明,那就打表
打表找规律大法好
文章写太长不好,剩下来的以后讲。
下次应该会多写几道例题。
别问我为什么退役了才写这个