数论基础理论

数论。。。

  • 整数理论

    • 带余除法与整除

      带余除法就是带有余数的除法,$被除数=除数\times商+余数$。

      $a\div b=q…r$,$a=bq+r$($0\le r<|b|$)

    • 取整

      • 下取整

        计作:$\lfloor x\rfloor$(或$floor(x)$)

        显然$q=\lfloor \dfrac ab\rfloor$

      • 上取整

        计作:$\lceil x\rceil$(或$ceil(x)$)

      $\lceil \dfrac ab\rceil=\lfloor \dfrac{a+b-1}{b}\rfloor$

      $a<\lfloor \dfrac cb\rfloor\leftrightarrow ab<c-b+1$

      $a\le\lfloor \dfrac cb\rfloor\leftrightarrow ab\le c$

      $a>\lfloor \dfrac cb\rfloor\leftrightarrow ab>c$

    • 最大公约数与最小公倍数

      $a$ 与 $b$ 的最大公因数记为 $gcd(a, b)$

      $a$ 与 $b$ 的最小公倍数记为 $lcm(a, b)$

      $ab = gcd(a, b)lcm(a, b)$

      • 欧几里得算法

        $gcd(a,b)=\cases{gcd(b,a~mod~b)&$b\not=0$\\a&$b=0$}$

      • 拓展欧几里得算法

        给定 $a, b, c$,求关于 $x, y$ 的方程 $ax + by = c$ 的任意一组解

        只有$gcd(a, b)|c $时有解

        假设我们已经求出了$ b \times x’ + (a ~mod ~b) \times y’ = c$ 对于$x’, y’$ 的解

        所以得到则 $b \times x’ + (a − b\times \lfloor \dfrac ab\rfloor)\times y’ = c$

        所以 当前方程$x = y’, y = x’ − \lfloor\dfrac ab\rfloor y’$

        想欧几里得算法一样递归下去

      • 类欧几里得算法

        我太弱了,看这篇博客吧。

        Here

    • 质数和合数

      • 质数

        有且仅有两个因子的数是质数

        • 质数的个数是无穷的
        • 若 $a$ 为大于 $1$ 的整数,在区间 $(a, 2a]$ 中必存在至少一个质数
        • 若 $n$ 为正整数,在 $n^2$ 到 $(n + 1)^2$ 之间至少有一个质数
        • 若 $n$ 为大于 $1$ 的整数,在 $n$ 到 $n!$ 之间至少有一个质数
        • 质数的个数公式 $π(n)$ 约等于 $\dfrac{n}{log(n)}$

        除了第一个,和第四个可以由第二个推出(然而第二个我不会),我都不会

      • 判断质数

        • 定义法 $O(n)$

        • 试除法 $O(\sqrt{n})$

        • 预处理版试除法

          预处理 $O(\sqrt n)$

          查询 $O(\dfrac{\sqrt n}{log_2n})$

        • 概率优化:(做法)大于等于5的质数模6一定等于1或5

        • Miller-Rabin:$O(log ^2_2n)$,基于费马小定理的非确定性算法。

      • 大数质因数分解 Pollard-rho

        定义函数 $f _x$ 为 $[0, n)$ 向 $[0, n)$ 的一个随机映射(据说通常表示为$f_x=x^2+C$,$C$为一个常数)

        设 $x1$ 为一个 $[0, n)$ 内的随机数,令 $x2 = f _{x1}$

        重复执行:

        • 令 $p = gcd(|x1 − x2|, n)$ 若 $p \not= 1$ 那么$ p$ 就是 $n$ 的一个因子并退出

        • 令 $x1 = f _{x1}$, $x2 = f _{f _{x2}}$

        • 若 $x1 = x2$ 那么说明陷入了循环,换一个新的随机函数 $f$与一个新的 $x1$,并令 $x2 = f _{x1}$

          原因:如果将$x, f _x, f _{f _x}\dots$ 这整个轨迹画出来,那么一定会形成一个 $\rho$型的环

  • 整数理论

    • 取模与同余

      • 模运算

        $a~ mod~ b = a − b \times \lfloor \dfrac ab\rfloor$

      • 同余的定义

        $a\equiv b(mod~p)\leftrightarrow a~mod~p=b~mod~p$

      • 线性同余方程

        $ax\equiv b(mod~p)$

        转换为 $ax + py = b$, 用拓展欧几里得算法即可

      • 中国剩余定理

        求解关于 $x$ 的方程 $\forall i \in [1, k], x \equiv x_i (mod ~m_i)$

        有一个十分巧妙的$O(\sum_{i=1}^klog_2m_i)$

        $M = \prod_{i=1}^ km_i$

        $\forall i\in[1,k],M_i=\dfrac{M}{m_i},M_i\times M_i^{-1}\equiv1(mod~m_i)$

        $x=\prod_{i=1}^kx_iM_iM_i^{-1}(mod~M)$

      • Lucas定理

        $gcd(x,y)\equiv gcd(\frac xp,\frac yp)\times gcd(x~mod~p,y~mod~p)\ \ (mod~p)$

    • 欧拉定理与费马小定理

      • 费马小定理

        如果$p$是质数,且$gcd(a,p)=1$,则$a^{p-1}\equiv1(mod~p)$

        注意费马小定理的反定理是错的,但是错误概率不大

      • Miller-Rabbin算法

        如果 $a^{p−1} \equiv 1 (mod ~p)$($a$ 为任意小于$p$ 的正整数)则可近似认为 $p$ 为素数
        多次用不同的 $a$ 来尝试 $p$ 是否为素数,可以将错误率降低到可接受范围,但是依然有合数可以通过(称为“伪素数”)

        • 二次探测

          如果 $p$ 是一个素数,那么对于 $x\in(0,p)$ ,若$x^2 ≡ 1 (mod ~p)$,则 $x = 1$ 或 $x = p − 1$

          重复执行以下步骤:

          • 若 $a^{p−1} \not\equiv 1 (mod~ p)$,那么 $p$ 不是质数,退出
          • 令 $t = p − 1$
          • 若 $t$ 是奇数,那么 $p$ 只可能是质数$2$,退出
          • 令$t=\dfrac t2$
          • 若 $a^t −1 (mod ~p)$,那么 $p$ 可能是质数,退出
          • 若 $a^t\not\equiv 1 (mod ~p)$,那么 $p$ 不是质数,退出
          • 回到 $3$ 操作
      • 欧拉定理

        • 欧拉函数

          对于正整数 $n$,令 $\phi(n)$ 表示比 $n$ 小的与 $n$ 互质的数的个数

          $\phi(n)$ 称为欧拉函数

          性质:

          • $n=\prod_{i=1}^kp_i^{q_i}$,$\phi(n)=n\prod_{i=1}^k\dfrac{p_i-1}{p_i}$
          • 对于素数$n$ ,$\phi(n)=n-1$
          • $\phi(1)=1$
          • 设$p$是质数,$\phi(p^k)=(p-1)p^{k-1}$
          • 若$gcd(x,y)=1$则$\phi(xy)=\phi(x)\phi(y)$
          • $\sum_{d|n}\phi(d)=n$

        $\forall gcd(a, n) = 1, a^{\phi(n)} \equiv 1 (mod ~n)$

      • 乘法逆元

        对于整数 $a, p$,如果存在 $x$ 满足 $ax \equiv 1 (mod ~p)$,那么 $x$是 $a$ 在模$ p$ 下的乘法逆元

        • 扩欧$ax+bp=1$
        • $x\equiv a^{p-2}(mod~p)$
        • $x\equiv a^{\phi(p)}(mod~p)$
      • RSA公钥系统

        额,看这吧。

        Here

    • 二次同余式与二次剩余

      • 二次同余式

        二次同余式是关于未知数的二次多项式的同余方程,形如$ax^2 + bx + c \equiv 0 (mod ~p)$

        形如 $x^2 \equiv a (mod~ p)$ 的二次同余式则称为最简二次同余式

      • 二次剩余

        • 剩余类

          所有与整数 $a$ 模 $p$ 同余的整数构成的集合叫做模$p$ 的一个剩余类,记作$ [a]$

        • 二次剩余

          假设 $p$ 是素数,$a$ 是整数,如果存在一个整数 $x$使得 $x^2 \equiv a (mod~ p)$,那么就称 $a$ 在 $p$ 的剩余类是二次剩余的

        • 二次非剩余(类似二次剩余)

          $a$ 是模 $p$ 的二次剩余的充要条件是 $a^{\frac{p−1}2} \equiv 1 (mod~ p)$

          $a$ 是模 $p$ 的二次非剩余的充要条件是 $a^{\frac{p−1}2} \equiv -1 (mod~ p)$

      • 二次互反律

        设 $a, p$ 是两个非零整数,我们定义$(\frac ap)$:若 $a$ 是模 $p$ 的二次剩余,则记$(\frac ap)= 1$ 否则记$(\frac ap)=-1$

        设$ p $和$ q $为不同的奇素数,则

        $(\frac qp)(\frac pq)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

    • 指数与原根

      • 指数

        对于两个互质的整数$a, p$,定义 $a$ 对模 $p$ 的阶为最小的满足 $a^x \equiv 1 (mod~ p)$ 的正整数$x$,记作 $\delta _p(a)$

        显然 $\delta _p(a)|\phi(p)$

        定理:$\delta _p(a^k) = \dfrac{\delta _p(a)}{gcd(\delta_p(a),k)}$

        求阶:因为 $\delta_p(a)|\phi(p)$,暴力枚举 $\phi(p)$ 的约数即可

      • 原根

        满足 $\delta_p(a) = \phi(p)$ 的 $a$ 称为 $p$ 的原根

        原根存在的条件:$2, 4, p^k, 2p^k$ 其中 p 表示奇质数

        • 原根一旦有就有 $\phi(\phi(p))$ 个
        • 设 $p$ 是奇质数,$g$ 是 $p$ 的原根,则 $g$ 或者$ g + p $是 $p^2$ 的一个原根
        • 设 $p$ 是奇质数,$g$ 是 $p^k$ 的一个原根,则 $g$ 与 $g + p^k$ 中的奇数是 $2p^k$ 的一个原根

        求法:枚举

    • BSGS算法

      求解关于 $x$ 的方程 $a^x ≡ b (mod p)$,其中 $a, b$ 与 $p$ 互质

      $\therefore a^{\phi(p)}\equiv a^1(mod~p)$

      所以我们可以在$O(\phi(p))$求解或判断无解

      可是最坏情况(质数)是$O(p)$的

      于是有了BSGS

      • 设一个参数 $l$,将 $a^0, a^1, a^2, \dots,a^{l−1}$ 存入hash

      • 枚举$k \le \dfrac{\phi(p)-1}l$

      • 判断$a^{kl+j}\equiv b(mod~ p)$是否有解

        即查询所有$a^j\equiv a^{-kl}b(mod~p)$

      显然$l=\sqrt{\phi(p)}$时最优

      预处理和查询都是$O(\sqrt{\phi(p)})$的

      如果查询多,可以调整$l$的值

  • 数论函数

    • 积性函数

      • 积性函数

        数论函数:定义域为正整数的函数

        积性函数:$\forall gcd(a, b) = 1$,满足 $f (ab) = f (a)f (b) $的函数
        完全积性函数:对于任意 $a, b$,满足 $f (ab) = f (a)f (b)$ 的函数
        积性函数的性质:如果 $f (x), g(x)$ 是积性函数,那么以下函数皆为积性函数

        • $h(x)=f(x^p)$

          $h(x)=f(x^p)=f(a^pb^p)=f(a^p)f(b^p)=h(a)h(b)$

        • $h(x)=f^p(x)$

          证明同上

        • $h(x)=f(x)g(x)$

          证明同上

        • $h(x) = \sum_{i|x}f (i)g(\frac xi)$

          不会证明

      • 常见的积性函数

        $e(n) = [n = 1]$

        $Id(n) = n$(大写i和小写d

        $1(n) = 1$ (啥?)

        $\sigma_k(n)=\sum_{d|n}d^k$

        $\phi(n)=\sum_{i=1}^n[gcd(i,n)=1]$

      • 常见积性函数的一些性质

        $\phi(ab) = \phi(a)\phi(b)\dfrac{gcd(a, b)}{ϕ(gcd(a, b))} = \phi(lcm(a, b))\phi(gcd(a, b))$
        $σ_0(ab) = \sum_{i|a}\sum_{j|b}[gcd(i, j) = 1]$

      • 狄利克雷卷积

        定义两个数论函数 $f , g$ 的狄利克雷卷积为$(f ∗ g)(n) = \sum_{d|n}f (d)g(\frac nd)$

        狄利克雷卷积的性质

        • 交换律:$f ∗ g = g ∗ f$
        • 结合律:$(f ∗ g) ∗ h = f ∗ (g ∗ h)$
        • 分配律:$f ∗ (g + h) = f ∗ g + f ∗ h$
        • 单位元:$f ∗ e = e ∗ f = f$
      • 常见的狄利克雷卷积

        $d(n)=\sum_{d|n}1\leftrightarrow d=1*1$

        $\sigma(n)=\sum_{d|n}d\leftrightarrow \sigma=1*d$

        $\phi(n)=\sum_{d|n}\mu(d)\frac dn\leftrightarrow \phi=\mu*Id$

        $e(n)=\sum_{d|n}\mu(d)\leftrightarrow e=Id*1$

    • 莫比乌斯反演

      • 容斥与反演

        • 容斥

          大家可能有几种看法:

          • 容斥就是隔一个数加上一个负号, 然后答案正好就对了
          • 容斥就是 $\sum_{i=0}^n(^n_i)(-1)^i=[n=0]$

          最一般的,可以对于每个贡献的条件$C_1,C_2\dots C_n$够着出$f_1,f_2\dots f_n$

          $\sum_{i=1}^ns(C_i)f_i=s(C_0)$

          $s(C_i)$表示在$C_i$下的贡献

        • 二项式反演

          $b(k)=\sum_{i=0}^k(-1)^i(_i^k)a(i)\leftrightarrow a(k)=\sum_{i=0}^k(-1)^i(_i^k)b(i)$

          $b(k)=\sum_{i=0}^k(_i^k)a(i)\leftrightarrow a(k)=\sum_{i=0}^k(-1)^{k-i}(_i^k)b(i)$

        • 莫比乌斯反演

          $f(n)=\sum_{d|n}g(d)\leftrightarrow g(n)=\sum_{d|n}f(d)\mu(\frac nd)$

    • 杜教筛

      • $\phi,\mu$前缀和

        $\Phi(n)=\sum_{i=1}^n\phi(i)=\sum_{i=1}^n(i-\sum_{d|i,d\not=i}\phi(d))=\dfrac{n\times(n+1)}2-\sum_{i=2}^n\Phi(\lfloor\dfrac ni\rfloor)$

        同理$M(n)=1-\sum_{i=2}^nM(\lfloor\dfrac ni\rfloor)$