avatar

OI数学专题笔记 - 2

OI数学专题笔记 - 2

素数的定义和判定

定义

如果 pp 只有 1 和 pp 两个印子,则 pp 为负数。

Miller-Rabin 素性测试

如果 nn 为素数,取 a<na < n ,设 n1=d×2rn - 1 = d \times 2^r ,则要么 ad1(modn)a^d \equiv 1 \pmod n ,要么 0i<r,s.t.ad×2i1(modn)\exists 0 \leq i < r, s.t. a^{d \times 2^i} \equiv -1 \pmod n 。(费马小定理的推广形式)

意思是:如果有一个素数 nn ,任取 1a<n1 \leq a < n ,将 n1n - 1 分解为 n1=d×2rn - 1 = d \times 2^r ,其中 dd 为奇数, 则有如下两条性质至少有一条满足:

  1. ad1(modn)a^d \equiv 1 \pmod n

  2. 0i<r,s.t.ad×2I1n1(mod1)\exists 0 \leq i < r, s.t. a^{d \times 2^I} \equiv -1 \equiv n - 1 \pmod 1

当任取 1a<n1 \leq a < n ,可能出现以下情况:

  1. 一条都不成立。

  2. 至少一条成立。

若一条都不成立,则说明这个数不是素数,若至少成立一条,则说明这个数有可能是素数。

所以算法流程为:找 kk 个数,全部进行素性测试,若都能通过,则认为这个数是素数,若有任意一个数不通过,则这个数不是素数。

一般来说,建议选八个质数,例如 {2, 3, 5, 7, 11, 13, 17, 37},这样的八个数可以保证算法在long long 范围内都不会出错。因为有人曾经用超级计算机枚举 long long 内的所有数进行算法检查。

逆元

定义与求法

如果 gcd(a,m)=1gcd(a, m) = 1 且存在唯一的 bb 使得 a×b1(modm)a \times b \equiv 1 \pmod m1b<n1 \leq b < n ,则 bbaa 在模 mm 意义下的逆元。

  • 费马小定理:对于任何一个质数 pp ,有 ap11(modp)a^{p - 1} \equiv 1 \pmod p ,其中 1a<p1 \leq a < p 。因为 ap11(modp)a^{p - 1} \equiv 1 \pmod p ,所以 a×ap21(modp)a \times a^{p - 2} \equiv 1 \pmod p

  • 欧拉定理:对于任意的一个数 mm ,有 aϕ(m)1(modm)a^{\phi(m)} \equiv 1 \pmod m 。其中 ϕ(m)\phi(m) 叫做欧拉函数,表示 11 ~ mm 中有多少个数与 mm 互质。当 mm 为质数时,ϕ(m)=m1\phi(m) = m - 1 ,就变成了费马小定理。

所以,当模数 pp 为质数时, aa 的逆元为 ap2a^{p - 2} ;当模数 mm 为任意数时, aa 的逆元为 aϕ(m)a^{\phi(m)}

ϕ(m)=m(11p1)(11p2)...(11pk)\phi(m) = m(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_k}) ,其中 p1pkp_1 \cdots p_kmm 的因子。

线性求逆元

如何求 11 ~ nn 所有数对质数 pp 的逆元?

如果对 11 ~ nn 每一个数计算它的 p2p - 2 次方,则时间复杂度是 O(nlogn)O(nlogn) 的,有没有方法 O(n)O(n) 的将它们求出来呢?

1in,p=ki+rki+r0(modp)kr1+i10(modp)i1kr1(modp)i1kr1(modp)i1pi(p mod i)1\begin{array}{l} \forall 1 \leq i \leq n, p = ki + r \\ ki + r \equiv 0 \pmod p \\ kr^{-1} + i^{-1} \equiv 0 \pmod p \\ i^{-1} \equiv -kr^{-1} \pmod p \\ i^{-1} \equiv -kr^{-1} \pmod p \\ i^{-1} \equiv - \lfloor \frac{p}{i} \rfloor (p\ mod\ i)^{-1} \end{array}

ExGCD

  • 给定 a,ba, b ,已知 g=gcd(a,b)g = gcd(a, b) ,求 x,yx, y ,使得 ax+by=gax + by = g

如果已知一组解 x,yx, y ,则其他解一定为 kbgcd(a,b),kagcd(a,b)k \cdot \frac{b}{gcd(a, b)}, -k \cdot \frac{a}{gcd(a, b)}

gcd(a,b)gcd(a, b) 求到最后一定为 gcd(g,0)gcd(g, 0) ,显然此时 x=1,y=0x = 1, y = 0 为一组解,所以现在需要将这组解向上推出两数为 a,ba, b 时的解。

因为 gcd(a,b)=gcd(b,agcd(a, b) = gcd(b, a % b) ,若已知 bx+ab \cdot x' + a % b \cdot y' = g ,可以将式子进行如下变换:

bx+(abab)y=gay+(xaby)b=g\begin{array}{l} b \cdot x' + (a - b \cdot \lfloor \frac{a}{b} \rfloor) \cdot y' = g \\ a \cdot y' + (x' - \lfloor \frac{a}{b} \rfloor \cdot y') \cdot b = g \end{array}

观察方程组

{ax+by=gbx+(abab)y=g\left \{ \begin{array}{l} a \cdot x + b \cdot y = g \\ b \cdot x' + (a - b \cdot \lfloor \frac{a}{b} \rfloor) \cdot y' = g \end{array} \right.

则可以得到:

{x=yy=xaby\left \{ \begin{array}{l} x = y' \\ y = x' - \lfloor \frac{a}{b} \rfloor \cdot y' \end{array} \right.

所以在计算 gcd(a,b)gcd(a, b) 时进行计算即可。

裴蜀定理

给定 a,b,ca, b, c ,则 ax+by=cax + by = c 有整数解的充要条件是 gcd(a,b)cgcd(a, b) | c

中国剩余定理

目的

问题定义:给定 NN 个方程,形式均为 xbi(modmi)x \equiv b_i \pmod {m_i} ,求 xx

这个问题问的也就是求一个 xx 使它满足 xb(modlcm(m1,m2,,mn))x \equiv b \pmod {lcm(m_1, m_2, \cdots, m_n)}

所以中国剩余定理的用处就是求 bb

大数翻倍法

假设只有两个方程:

xb1(modm1)xb2(modm2)\begin{array}{l} x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \end{array}

不妨设 m1m2m_1 \geq m_2

b1b_1b1,b1+m1,b1+2m1,b1+3m1,b_1, b_1 + m_1, b_1 + 2m_1 ,b_1 + 3m_1 , \cdots ,这样得到的 b1b_1 是显然满足第一个方程的,所以只需要逐一枚举计算 b1+km1b2(modm2)b_1 + k \cdot m_1 \equiv b_2 \pmod {m_2} 即可得到 x=b1+km1x = b_1 + k \cdot m_1

则对 nn 个方程进行 n1n - 1 次合并即可。

这个方法不正统,不过事实上不怎么会被卡。

ExGCD法

假设只有两个同余方程:

xb1(modm1)xb2(modm2)\begin{array}{l} x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \end{array}

x=k1m1+b1=k2m2+b2x = k_1m_1 + b_1 = k_2m_2 + b_2

所以 k1m1k2m2=b2b1k_1m_1 - k_2m_2 = b_2 - b_1 ,设 g=gcd(m1,m2),k1m1=x,k2m2=yg = gcd(m_1, m_2), k_1m_1 = x, k_2m_2 = y ,令 b2b1=grb_2 - b_1 = g \cdot r

则解出 x,yx', y' 满足 xm1+ym2=gx'm_1 + y'm_2 = g 再分别乘 rr 即可求出 k1,k2k_1, k_2 ,带回即可求出所求的数。

且根据裴蜀定理,当同余方程有解时 rr 一定为整数。

对于 nn 个方程,则对 nn 个方程进行 n1n - 1 次合并即可。

文章作者: Ender
文章链接: https://www.ender.xin/post/176f48fe.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's blog
打赏
  • 微信和支付宝
    微信和支付宝

评论