OI数学专题笔记 - 2
素数的定义和判定
定义
如果 p 只有 1 和 p 两个印子,则 p 为负数。
Miller-Rabin 素性测试
如果 n 为素数,取 a<n ,设 n−1=d×2r ,则要么 ad≡1(modn) ,要么 ∃0≤i<r,s.t.ad×2i≡−1(modn) 。(费马小定理的推广形式)
意思是:如果有一个素数 n ,任取 1≤a<n ,将 n−1 分解为 n−1=d×2r ,其中 d 为奇数, 则有如下两条性质至少有一条满足:
-
ad≡1(modn)
-
∃0≤i<r,s.t.ad×2I≡−1≡n−1(mod1)
当任取 1≤a<n ,可能出现以下情况:
-
一条都不成立。
-
至少一条成立。
若一条都不成立,则说明这个数不是素数,若至少成立一条,则说明这个数有可能是素数。
所以算法流程为:找 k 个数,全部进行素性测试,若都能通过,则认为这个数是素数,若有任意一个数不通过,则这个数不是素数。
一般来说,建议选八个质数,例如 {2, 3, 5, 7, 11, 13, 17, 37}
,这样的八个数可以保证算法在long long
范围内都不会出错。因为有人曾经用超级计算机枚举 long long
内的所有数进行算法检查。
逆元
定义与求法
如果 gcd(a,m)=1 且存在唯一的 b 使得 a×b≡1(modm) 且 1≤b<n ,则 b 为 a 在模 m 意义下的逆元。
-
费马小定理:对于任何一个质数 p ,有 ap−1≡1(modp) ,其中 1≤a<p 。因为 ap−1≡1(modp) ,所以 a×ap−2≡1(modp) 。
-
欧拉定理:对于任意的一个数 m ,有 aϕ(m)≡1(modm) 。其中 ϕ(m) 叫做欧拉函数,表示 1 ~ m 中有多少个数与 m 互质。当 m 为质数时,ϕ(m)=m−1 ,就变成了费马小定理。
所以,当模数 p 为质数时, a 的逆元为 ap−2 ;当模数 m 为任意数时, a 的逆元为 aϕ(m) 。
ϕ(m)=m(1−p11)(1−p21)...(1−pk1) ,其中 p1⋯pk 为 m 的因子。
线性求逆元
如何求 1 ~ n 所有数对质数 p 的逆元?
如果对 1 ~ n 每一个数计算它的 p−2 次方,则时间复杂度是 O(nlogn) 的,有没有方法 O(n) 的将它们求出来呢?
∀1≤i≤n,p=ki+rki+r≡0(modp)kr−1+i−1≡0(modp)i−1≡−kr−1(modp)i−1≡−kr−1(modp)i−1≡−⌊ip⌋(p mod i)−1
ExGCD
- 给定 a,b ,已知 g=gcd(a,b) ,求 x,y ,使得 ax+by=g 。
如果已知一组解 x,y ,则其他解一定为 k⋅gcd(a,b)b,−k⋅gcd(a,b)a 。
而 gcd(a,b) 求到最后一定为 gcd(g,0) ,显然此时 x=1,y=0 为一组解,所以现在需要将这组解向上推出两数为 a,b 时的解。
因为 gcd(a,b)=gcd(b,a ,若已知 b⋅x′+a ,可以将式子进行如下变换:
b⋅x′+(a−b⋅⌊ba⌋)⋅y′=ga⋅y′+(x′−⌊ba⌋⋅y′)⋅b=g
观察方程组
{a⋅x+b⋅y=gb⋅x′+(a−b⋅⌊ba⌋)⋅y′=g
则可以得到:
{x=y′y=x′−⌊ba⌋⋅y′
所以在计算 gcd(a,b) 时进行计算即可。
裴蜀定理
给定 a,b,c ,则 ax+by=c 有整数解的充要条件是 gcd(a,b)∣c 。
中国剩余定理
目的
问题定义:给定 N 个方程,形式均为 x≡bi(modmi) ,求 x 。
这个问题问的也就是求一个 x 使它满足 x≡b(modlcm(m1,m2,⋯,mn)) 。
所以中国剩余定理的用处就是求 b 。
大数翻倍法
假设只有两个方程:
x≡b1(modm1)x≡b2(modm2)
不妨设 m1≥m2
令 b1 为 b1,b1+m1,b1+2m1,b1+3m1,⋯ ,这样得到的 b1 是显然满足第一个方程的,所以只需要逐一枚举计算 b1+k⋅m1≡b2(modm2) 即可得到 x=b1+k⋅m1。
则对 n 个方程进行 n−1 次合并即可。
这个方法不正统,不过事实上不怎么会被卡。
ExGCD法
假设只有两个同余方程:
x≡b1(modm1)x≡b2(modm2)
则 x=k1m1+b1=k2m2+b2
所以 k1m1−k2m2=b2−b1 ,设 g=gcd(m1,m2),k1m1=x,k2m2=y ,令 b2−b1=g⋅r
则解出 x′,y′ 满足 x′m1+y′m2=g 再分别乘 r 即可求出 k1,k2 ,带回即可求出所求的数。
且根据裴蜀定理,当同余方程有解时 r 一定为整数。
对于 n 个方程,则对 n 个方程进行 n−1 次合并即可。