数论前置知识部分学习笔记


写在最前

生活所迫。数论小白开始入门数论了。

前置知识

一些结论

  • 质数的密度为 \(\frac{1}{\text{log}n}\) ,即小于等于 \(n\) 的质数大约有 \(\frac{n}{\text{log}n}\) 个。
  • \(\sum_{1\le p\le n}\frac{1}{p}=O(\text{log}\text{log}n)\) ,其中 \(p\) 为质数。

GCD 相关

GCD

\(r|a,r|b \Leftrightarrow  r|(a-b),r|b \)

于是有 \((a,b)=(a-b,b)=(a\; mod\; b,b)\)

LCM

\([a,b](a,b)=a\cdot b\)

裴蜀定理

对于整数 \(a,b,c\),如果 \(ax+by=c\) 有整数解,那么一定有 \((a,b)|c\)

拓展 GCD

用于求解 \(ax+by=(a,b)\) 的任意整数解。

考虑在求 GCD 的过程中同时求出 \(x,y\) ,我们令 \(a’=b,b’=a\; mod\; b\) (操作一步以后)

如果递归下去,则相当于现在已经求得 \(a’x+b’y=(a’,b’)\) 的 \(x,y\) 了

\(b’=a\; mod \;b =a – a/b*b\) ,则 \(bx+(a-a/b*b)y=(a’,b’)=(a,b)\Rightarrow ay+b(x-a/b*y)=(a,b)\)

于是可以得到新的 \(x=y,y=x-a/b*y\)

这样可以求得一个任意解 \(x_0,y_0\) ,而一般题目会对解的范围有一定的要求,可以发现,经过下面调整,仍然是一个题目的解:\(x_o+\frac{b}{(a,b)},y_0-\frac{a}{(a,b)}\) 。

类 GCD

类欧几里得最基本的就是求 \(\sum_{x=0}^n \left \lfloor \frac{ax+b}{c} \right \rfloor\) ,其中 \(0<a,b,c,n\) ,为了方便,我们用 \(f(a,b,c,n)\) 来表示这个式子。

可以先理解一下这个式子的含义,如果把 \(\frac{ax+b}{c}\) 看作坐标系内的一条直线方程,那么这个式子求的就是从 \(0\le x\le n\) 内在 \(x\) 轴上方,直线下方的整点个数。

考虑 \(a\ge c\) 的时候,我们可以将式子分成两部分(整除的一部分可以提取出来):\(f(a,b,c,n)=\frac{n(n+1)}{2}\times \left \lfloor \frac{a}{c} \right \rfloor+(n+1) \times \left \lfloor \frac{b}{c} \right \rfloor+f(a\; mod \; c,b\; mod \; c,c,n)\) .

这样一来 \(a,b < c\) 了,之后根据其几何意义,我们可以考虑将直线反转到 \(y\) 轴上,变成求 \(y\) 轴到,如图所示:

这样经过反转以后,本来直线的斜率为 \(\frac{a}{c}\) ,此时变成了 \(\frac{c}{a}\) ,现在要求的整点个数,我们可以考虑从整个矩形减去 \(S\) 部分的整点。

为了方便表示,我们令 \(m= \left \lfloor \frac{an+b}{c} \right \rfloor\)

则有 \(\sum_{x=0}^n \left \lfloor \frac{ax+b}{c} \right \rfloor\\=\sum_{x=0}^n \sum_{j=1}^m \left \lfloor \frac{ax+b}{c} \right \rfloor \ge j \\ =\sum_{x=0}^n \sum_{j=0}^{m-1} \left \lfloor \frac{ax+b}{c} \right \rfloor \ge j+1 \\ = \sum_{x=0}^n \sum_{j=0}^{m-1} (ax+b) \ge cj+c \\ = \sum_{x=0}^n \sum_{j=0}^{m-1} x > \left \lfloor  \frac{cj+c-b-1}{a} \right \rfloor  \\ = \sum_{j=0}^{m} n- \left \lfloor  \frac{cj+c-b-1}{a} \right \rfloor \\= nm-f(c,c-b-1,a,m-1)\)

因为之前 \(a,b < c\) 所以此时交换了 \(a,c\) 的位置,又回到了 \(a\ge c\) 的情况。

因为这样的形式类似于 GCD 的求解方式,所以也被称为类欧几里得。

剩下类欧几里得还有两种形式(推导方式方式类似,就不再赘述):

  • \(g(a,b,c,n)=\sum_{i=0}^n i \lfloor\frac{ai+b}{c}\rfloor\)
    • \(a \ge c\) or \(b \ge c\) 时,\(g(a,b,c,n)=(\frac{a}{c})n(n+1)(2n+1)/6+(\frac{b}{c})n(n+1)/2+g(a \bmod c,b \bmod c,c,n)\)
    • 否则 \(g(a,b,c,n)=\frac{1}{2} (n(n+1)m-f(c,c-b-1,a,m-1)-h(c,c-b-1,a,m-1))\)
  • \(h(a,b,c,n)=\sum_{i=0}^n\lfloor \frac{ai+b}{c} \rfloor^2\)
    • \(a \ge c\) or \(b \ge c\) 时,\(h(a,b,c,n)=(\frac{a}{c})^2 n(n+1)(2n+1)/6 +(\frac{b}{c})^2 (n+1)+(\frac{a}{c})(\frac{b}{c})n(n+1)+h(a \bmod c, b \bmod c,c,n)+2(\frac{a}{c})g(a \bmod c,b \bmod c,c,n)+2(\frac{b}{c})f(a \bmod c,b \bmod c,c,n)\)
    • 否则 \(h(a,b,c,n)=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)\)

素数相关

暴力判断

从 \(2\) 开始尝试是否是 \(x\) 的约数,直到 \(\sqrt{x}\) 。

欧拉定理

欧拉函数是小于或等于 \(n\) 的正整数中与 \(n\) 互质的数的数目,用 \(\varphi (n)\) 表示。

其中 \(\varphi(n)\) 有通项公式 \(\varphi(n) = n\prod _{i=1}^{x}(1-\frac{1}{p_i})\) 其中 \(p_1,p_2,\cdots ,p_x\) 为 \(n\) 的所有质因数。

利用通项公式,我们可以直接求解欧拉函数的值:

欧拉定理 :

  • 如果 \((a,m)=1\) ,则 \(a^{\varphi(m)}\equiv 1 (mod \;m)\) ;

扩展欧拉定理:

  • 如果 \((a,m)\neq 1\) ,则 \(a^b\equiv a^{\text{min}(b,b\; mod\; \varphi(m)+\varphi(m))} (mod \;m)\) 。
【例1】BZOJ 3884

【BZOJ3884】上帝与集合的正确用法

费马质数判定法

根据费马小定理,\(a^{p-1}\equiv 1 (mod\; p)\) ,其中 \(p\) 是质数,\(a\) 是整数。

于是我们可以考虑随机一个 \(a\) ,计算 \(a^{n-1}\; mod\; n\) 是否为 \(1\) ,如果不为 \(1\) ,那么肯定不是质数,否则需要继续尝试数次。

如果 \(a\equiv 1(mod\; n),a_1\equiv a_2\equiv \cdots \equiv a_s \not\equiv 1(mod \; n)\),则有 \((a\cdot a_{i})^{{n-1}}\equiv a^{{n-1}}\cdot a_{i}^{{n-1}}\equiv a^{{n-1}}\not \equiv 1{\pmod {n}}\) ,也就是说所有的 \(a\cdot a_i(1\le i\le s)\) 都满足 \(a\cdot a_i\not\equiv 1 (mod\; n)(1\le i\le s)\) 。

于是可以得到,对于一个合数而言,我们找到一个 \(a\) 使得 \(a^n\equiv 1(mod \;n)\) 的概率是小于 \(\frac{1}{2}\) ,这样的单次检验正确率已经比较可观了。

不过费马质数判定法有一个致命的弱点,即 Carmichael number 如果用费马质数判定法来检验的话,会被误判。

MiLLer Rabin

基于 Fermat 质数检验法的改进。

Fermat 质数检验法,每次都是检验 \(a^{n-1}\equiv 1(mod\; n)\) 是否成立,现在假设 \(n-1=2^k\cdot t\) 。

我们考虑先检验 \(a^t\) ,然后不断翻倍验证。

因为对于一个质数 \(p\) 有 \(x^2\equiv 1(mod \; p)\Leftrightarrow  x\equiv \pm 1 (mod \; p)\) 。于是有从 \(a^t\) 开始往上倍增的时候一定一直满足 \(mod \; p\) 为 \(\pm 1\) 。

可以证明检验的单次正确率大于 \(\frac{1}{2}\) 。证明太复杂,省略了。

对于不同范围数的 MiLLer-Rabin 检验可以使用不同的 \(a\),具体是:

  • int 范围内只需检查 \(2, 7, 61\)
  • long long 范围 \(2, 325, 9375, 28178, 450775, 9780504, 1795265022\)
  • \(3\cdot 10^{15}\) 内 \(2, 2570940, 880937, 610386380, 4130785767\)
  • \(4\cdot 10^{13}\) 内 \(2, 2570940, 211991001, 3749873356\)

质因数分解

暴力分解一个数 \(n\) 的时间复杂度是 \(O(\sqrt{n})\) 。

对于一个质数 \(p\) 在 \(n!\) 中出现的次数为 \(\left \lfloor \frac{n}{p}\right \rfloor+ \left \lfloor \frac{n}{p^2}\right \rfloor+\left \lfloor \frac{n}{p^3}\right \rfloor+\cdots \)

Pollard Rho

分解一个合数的高效算法。

可以将问题转化为求一个合数 \(n\) 的非平凡因子(非平凡因子是指除了 \(1\) 和本身以外的最小约数)。

从生日悖论可以得到,我们在 \([1,n]\) 内随机 \(O(\sqrt{n})\) 次整数,就有大概率出现两个相同的数。

于是我们可以考虑随机一个 \(x_0\) 出来,然后有一个多项式 \(f(x)\),我们令 \(x_i=f(x_{i-1})\) 。

也就是通过大概 \(\sqrt{n}\) 次,我们可以得到 \(x_i\equiv x_j (mod \; n) (i < j)\) ,因为 \(f(x)\) 固定,所以之后就会有 \(x_{i+1}\equiv x_{j+1} ,x_{i+2}\equiv x_{j+2},\cdots  \) ,也就是说 \(x_i\) 数列是 \(\rho\) 形的,也就是会入一个环,之后一直在环内循环往复。

因为得到这样的 \(x_i,x_j\) ,我们就可以得到 \(|x_i-x_j|\equiv 0 (mod \; n)\) 。

考虑如何找到这样的循环节,显然把所有的 \(x_i\) 都保存下来不太现实,因为 \(n\) 可能会比较大。

有一个方式是用两个指针,一个指针每次走一步,另一个指针每次走两步,这样当后一个指针入环以后,显然最多再进行环长步数就一定会重合(从奇偶性考虑),也就是找到循环节重合的位置时间复杂度为 \(O(\sqrt{n})\) 。

而我们要找的是非平凡因子,显然合数非平凡因子一定 \(\le \sqrt{n}\) ,我们令 \(p=\sqrt{n}\) ,那么我们只需要在 \(mod \; p\) 意义下找这样的 \(x_i,x_j\) ,这样找到一个非平凡因子的期望时间复杂度是 \(O(n^{\frac{1}{4}})\) 。

【例2】LOJ6466

模版题。

MiLLer-Rabin 判断质数。

pollard_rho 分解一个非平凡因子。

输入输出部分用字符串操作一下,中间过程用 __int128 。

用上面的模版可以获得 \(80\) 分,能够处理到 \(10^{25}\) 。

素数个数

令 \(\pi (n)\) 表示 \(\le n\) 的素数个数。

最前面提到了,素数个数大约是 \(O(\frac{n}{logn})\) 级别的。

可以用欧拉筛在 \(O(n)\) 的时间复杂度内求得 \(\pi (n)\) 。

考虑更优的做法。

我们用 \(f(n,m)\) 表示 \(\le n\) 的正整数中因子不含有 \( p_1,p_2,\cdots ,p_m\) 的个数,其中 \( p_1,p_2,\cdots ,p_m\) 是按照顺序从小到大排列的质数。

容易发现 \(f(n,m)=f(n,m-1)-f(\left \lfloor \frac{n}{p_m} \right \rfloor,m-1)\) ,即去掉能被 \(p_m\) 整除但是不能被 \(p_1,p_2,\cdots ,p_{m-1}\) 整数的部分。而且 \(f(n,1)=n-\left \lfloor \frac{n}{p_1} \right \rfloor\) ;当 \(p_m^2 > n\) 的时候, \(f(\left \lfloor \frac{n}{p_m} \right \rfloor,m-1)=1\) (因为只包含 \(p_m\) ) 本身。

这样来做,可以保证时间复杂度是 \(O(n^{\frac{3}{4}})\) 。

模运算相关

线性同余方程组

由 \(n\) 个方程 \(x\equiv x_i(mod \; m_i)\) 组成的方程组,求解 \(x\) 。

中国剩余定理

前提: \(m_1,m_2,\cdots ,m_n\) 两两互质

令 \(M=\prod_{i=1}^n m_i,M_i=\frac{M}{m_i}\) 以及 \(M_i^{-1}\) 为 \(M_i \; mod \; m_i\) 的逆元,则有 \(x\equiv \sum_{i=1}^nx_iM_iM_i^{-1}(mod \; M)\) 。

【证明】

考虑 \((x_iM_iM_i^{-1})\; mod \; m_j\) 的结果:

  • 当 \(i = j\) 时,\(M_i^{-1}\) 为 \(M_i\; mod \; m_i\) 的逆元,所以 \((x_iM_iM_i^{-1})\equiv x_i(mod \; m_i)\) ;
  • 当 \(i\neq j\) 时,\(M_i=\frac{M}{m_i}\) 其中应该包含了 \(m_j\) ,则 \((x_iM_iM_i^{-1})\equiv 0(mod \; m_j)\) 。

所以 \(x\equiv x_i (mod \; m_i)\) 显然成立。

一般情况的解法

所谓一般情况,其实就是考虑\(m_1,m_2,\cdots ,m_n\) 两两存在不互质的时候如何解。

考虑增量法来解线性同余方程组。即每次合并两个方程为一个方程,不断这样的往复操作,直到只剩下一个方程为止。

假设当前有两个方程 \(x\equiv a(mod\; b)\\x\equiv c(mod\; d)\) 。

由第一个方程可以得到 \(x=bt_1+a\) ,其中 \(t_1\) 为任意整数,于是有 \(bt_1+a\equiv c(mod\; d)\) ,也就是 \(bt_1+a+dt_2=c\) ,即 \(bt_1+dt_2=c-a\) 。

这个方程中有两个未知数 \(t_1,t_2\) ,我们可以考虑通过拓展 GCD 来求得一个任意解。

于是可以得到 \(x\equiv bt_1+a(mod \; [b,d])\) 。

【例3】NOI2018 屠龙勇士
【例4】Codeforces338D GCD Table

【Codeforces338D】GCD Table

如果 \((a,m)=1\) ,记 \(x\) 是最小的正整数使得 \(a^x\equiv 1 (mod \; m)\) ,我们称这样的 \(x\) 为 \(a\) 模 \(m\) 的阶,计作 \(\delta _m(a)=x\)。

因为 \(a^{\varphi(m)}\equiv a^x\equiv 1 (mod \; m)\) 所以有 \(x|\varphi(m)\) 。于是求阶可以通过枚举 \(\varphi(m)\) 的因数来得到。

原根

如果\((a,m)=1\) ,且满足 \(\delta_m(a)=\varphi(m)\) ,那么 \(a\) 为模 \(m\) 的原根。

有原根的数有 \(1,2,4,p^a,2p^a\) ,其中 \(p\) 为奇质数。

【定理】如果正整数 \(m\) 有原根,那么一定有 \(\varphi(\varphi(m))\) 个原根。

【性质】原根 \(a\) 的幂次在模 \(m\) 的意义下有周期,且周期为 \(p-1\) 。

BSGS

如果 \((a,p)=1\) ,对于求解形如 \(a^x\equiv b(mod \; p)\) 的 \(x\) ,我们可以用 BSGS 来做。

因为要求解的这样的 \(x\) 满足 \(0\le x < p\) ,考虑把 \(x\) 拆成两部分,\(x=A\left \lceil p \right \rceil-B\) ,显然这其中 \(0\le A,B\le \left \lceil p \right \rceil\) 。

现在有 \(a^x\equiv a^{A\left \lceil p \right \rceil-B}\equiv b(mod \; p) \Rightarrow a^{A\left \lceil p \right \rceil}\equiv ba^B(mod \; p) \) 。

于是考虑预处理出所有的 \(ba^B\; mod\; p\) 的结果存在 hash 表中,然后枚举所有的 \(A\),尝试在 hash 表中查找是否存在这样的 \(a^{A\left \lceil p \right \rceil} \; mod \; p\) 。

这样的做法时间复杂度为 \(O(\sqrt{p})\) 。

拓展BSGS

即当 \((a,p)\neq 1\) 的时候,如何求解形如 \(a^x\equiv b(mod \; p)\) 的 \(x\) 。

考虑把 \(a,p\) 变成互质的。

每次取 \(d=(a,p)\) ,如果 \(d\not | b\) ,那么 \(a^x\equiv 0 (mod\; p\cdot d)\) 而 \(b\not \equiv 0 (mod\; p\cdot d)\) ,显然无解。

如果 \(d| b\) 那么就可以 \(a^x\equiv b(mod \; p) \Rightarrow a^{x-1}(\frac{a}{d})\equiv \frac{b}{d}(mod\; \frac{p}{d})\Rightarrow a^{x-1}\equiv \frac{b}{a}(mod\; \frac{p}{d})\)  不断递归,直到 \(d=1\) ,然后跑 BSGS 。

显然每次 \(d\ge 2\) ,所以这部分的时间复杂度为 \(O(logp)\) 。

假设这样操作了 \(k\) 次,那么其实求的是 \(a^{x-k}\equiv b(mod \; p)\) ,如果存在解 \(x < k\) ,会导致计算不出解。不过可以发现 \(k\le log(m)\) ,所以可以考虑对于这样的 \(x\) ,暴力枚举判断一下是否可行。

【例5】SDOI 2011 计算器

第一问就是用快速幂。

第二问用扩展 GCD 求出任意解,调整成最小的非负数解。

第三问因为没有保证互质,所以需要用扩展 BSGS 求解。

【例6】BZOJ1319 Discrete Roots

【BZOJ1319】Discrete Roots

Lucas 定理

\(\begin{pmatrix}n\\m\end{pmatrix}\equiv \begin{pmatrix}n\; mod\;p\\m\; mod\; p\end{pmatrix} \times \begin{pmatrix}\left \lfloor \frac{n}{p} \right \rfloor\\\left \lfloor \frac{m}{p} \right \rfloor\end{pmatrix} (mod \; p)\)  .

很多情况下,我们可以在 \(p\) 进制的意义下考虑 \(n,m\) 。

【例7】51nod 1778 小Q的集合

【51nod1778】小Q的集合

【例8】国家集训队 礼物

【国家集训队】礼物

Stern-Brocot Tree

Stern-Brocot Tree 是一种存入所有既约分数的一种形式。

他从 \(\frac{0}{1}\) 、 \(\frac{1}{0}\) 开始,每次在下一层插入两个相邻分数 \(\frac{a}{b}\) 和 \(\frac{c}{d}\) 之间的分数 \(\frac{a+c}{b+d}\) 。

它可以用一个二叉树的形式来表示,如下图:

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 44,605

Categories

Archive

Comments