基础数论

素数,约数,同余。

基础数论

常见的思维方法有:观察与分析、概括与抽象、分析与综合、特殊与一般、类比、归纳和演绎等;

常见的数学思想有:函数与方程思想、数形结合思想、分类讨论思想、转化(化归)思想等。

之所以先介绍这些,是因为这些东西确实很重要,在算法竞赛中蕴含得特别多,最常见的就是分类讨论,其他思想其实也特别多。

素数

素数的判定

枚举 22n\sqrt n 的数暴力判定。

素数筛

主要掌握埃氏筛和线性筛,并理解二者的原理,会魔改。

素因数分解

单个数素因数分解

对单个数的素因数分解,只需要从 22 枚举到 n\sqrt n ,对于每次枚举到的约数,不断让 nn 除之,统计除法次数,直到除不开。最后如果剩下的部分大于 11 ,则剩下的部分也是一个素数。可以证明,这样做下去我们只有在枚举到质数的时候才会真正做除法。

阶乘素因数分解

本需求会在高精度组合数计算中被用到。

分别对每个数进行分解的复杂度是 O(nn)O(n\sqrt n) ,数据范围比较大的时候难以承受。

另一种方法是先筛出 nn 范围内的所有素数,然后枚举素数,统计每个素数的贡献,即直接统计每个素数在阶乘中出出现了多少次,手段是不断除以这个素数pp,第kk次做除法得到的商,就代表有多少11nn 之间的数含有pp的最高次数是pkp^k。这种方法需要O(n)O(n)预处理素数,然后O(logpn)O(\sum \log_pn) 的时间统计所有素数的贡献。考虑到 11nn 的素数个数大约是O(nlnn)O(\frac{n}{\ln n})级别的,所以做放缩,知logpnnlnnlog2n\sum \log_p n \leq \frac{n}{\ln n} \log_2 n ,利用换底公式可知右式的渐进上界是 O(n)O(n)

参考代码如下:

// flag = 1 或 -1
void split(int n, int flag) {
    for (int i = 0; i < cnt; i++) {
        int p = prime[i];
        while (p <= n) {
            primeidx[i] += (flag * (n / p));
            p = p * prime[i];
        }
    }
}

约数

约数之和

求一系列数的乘积所得到的数的所有的约数之和。

先对每个数做素因数分解,然后使用生成函数的思想,可知最后的结果为

ans=i=1kj=0αipijans = \prod_{i = 1}^{k}\sum_{j = 0}^{\alpha_i}p_{i}^j

根据数据范围,选择使用秦九韶算法,分治或者等比数列求和公式进行计算即可。

最大公约数

辗转相除

最常用的方法。

更相减损

弱化版的辗转相除。

高精度gcd

高精度gcd常用更相减损术去做,因为高精度的取模不好写。

互素与欧拉函数

欧拉函数的定义是:ϕ(x)\phi(x)定义为 11xx 中与 xx 互素的数的个数。

容易发现,对素数 pp 来说,ϕ(p)=p1\phi(p) = p - 1

ϕ(x)\phi(x) 的计算公式容易理解:

ϕ(x)=x×(11p1)×(11p2)...×(11pk)\phi(x) = x \times(1 - \frac{1}{p_1})\times(1 - \frac{1}{p_2})...\times(1 - \frac{1}{p_k})

可以从概率的角度/容斥原理的角度去考虑这个公式(有多大概率取到不是pip_i的倍数的数)。

考虑 c=a×bc = a\times b,如果有 gcd(a,b)=1\gcd(a, b) = 1 ,则由上述计算公式中,可以发现 ϕ(c)=ϕ(a)×ϕ(b)\phi(c) = \phi(a)\times \phi(b) (因为没有相同素因子)

如果 gcd(a,b)1\gcd(a,b) \ne 1 ,倘若 aa 为素数,那么也是有很好的性质的。因为 aa 为素数,且 gcd(a,b)1\gcd(a, b) \neq 1 ,所以 gcd(a,b)=a\gcd(a, b) = a ,考虑到 ϕ(a)\phi(a)ϕ(b)\phi(b) 的计算式,可以发现 ϕ(c)=a×ϕ(b)\phi(c) = a \times \phi(b)

利用线性筛,可以 O(n)O(n) 的时间预处理出 ϕ(x)\phi(x)

同余

贝祖定理

gcd(a,b)=d\gcd(a, b) = d ,那么存在整数 x,yx, y ,使得 ax+by=dax + by = d​ 成立。

显然,若 dd 不能整除 cc ,那么 ax+by=cax + by = c​ 一定没有整数解。

特殊地,gcd(a,b)=1\gcd(a, b) = 1 时,存在整数 x,yx, y ,使得 ax+by=1ax + by = 1 成立。

中国剩余定理

普通CRT

对于同余方程组

{xa1(mod m1)xa2(mod m2)...xan(mod mn)\begin{cases} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2)\\ ...\\ x\equiv a_n(mod\ m_n)\\ \end{cases}

其中gcd(mi,mj)=1\gcd(m_i, m_j) = 11i,jn,ij1\leq i, j\leq n,i \neq j

M=i=1nmiM = \prod\limits_{i = 1}^nm_iMi=MmiM_i = \frac{M}{m_i}Mi1Mi1(mod mi)M_i^{-1}M_i\equiv1(mod\ m_i)

xi=1nMi1Mibi(mod mj),1jnx\equiv\sum\limits_{i= 1}^{n}M_i^{-1}M_ib_i(mod\ m_j),\forall 1\leq j\leq n

即我们给出了一个构造 $x $ 的方式。容易验证上式成立。

在求Mi1M_i^{-1} 时,注意到gcd(Mi1,mi)=1\gcd(M_i^{-1}, m_i) = 1 ,所以可以使用 exgcd 进行求解,而使用其他的方法求可能会求不出来(exgcd 只要有数和模数互素即可,而其他的方法需要模数是素数)。

exCRT

对于上述同余方程组,当不满足模数两两互素的时候,要想构造出 xx ,就需要使用扩展中国剩余定理了。

扩展中国剩余定理的思路是逐步两两合并方程:

{xa1(mod m1)xa2(mod m2)\begin{cases} x\equiv a_1(mod\ m_1)\\ x\equiv a_2(mod\ m_2) \end{cases}

改写成等式:

{x=m1p+a1x=m2q+a2\begin{cases} x = m_1p+a_1\\ x = m_2q+a_2 \end{cases}

需要有合适的整数使得p,qp, q 都是整数,所以 m1pm2q=a2a1m_1p - m_2q = a_2 - a_1 要有整数解,所以gcd(m1,m2)(a2a1)\gcd(m_1, m_2)\mid(a_2 - a_1) 才能保证有合适的 xx

费马小定理

主要用来求解模数是质数时的逆元。

如果 gcd(a,p)=1\gcd(a,p) = 1 ,那么 apa(mod p)a^p \equiv a(mod\ p) ,特别的,当 pp 为质数时,有 ap11(mod p)a^{p - 1}\equiv1(mod\ p)

哥德巴赫猜想

TODO

虽然是猜想,但是在很大的范围内验证是对的,所以有时候会用来做一些判断。

exgcd

用于求解二元一次方程的整数解,很多时候是求解包含逆元未知数的二元一次方程。

exgcd 的原理是,考虑辗转相除的过程,gcd(a, b) = gcd(b, a % b), b != 0

不妨设 gcd(a,b)=d\gcd(a, b) = d ,第 ii 次迭代时得到的方程是 aix+biy=da_ix + b_iy = d ,则有:

anx+bny=an+1x+bn+1y=da_nx + b_ny = a_{n + 1}x + b_{n + 1}y = d

进一步,使用 gcd(a,b)=gcd(b,a%b)\gcd(a, b) = \gcd(b, a \% b) (在没有到递归边界的时候),有:

anx+bny=bnx+(an%bn)y=da_nx + b_ny = b_nx + (a_n \% b_n)y = d

利用等式 a%b=a[ab]ba \% b = a -[ \frac{a}{b}]b​,代换之后有:

anx+bny=bnx+(an[anbn]bn)y=da_nx + b_ny = b_nx + (a_n -[ \frac{a_n}{b_n}]b_n)y = d

线性同余方程

形如 axb(mod m)ax\equiv b(mod\ m)​ ,可以转化为 ax+my=bax + my = b​ ,根据贝祖定理,有整数解的充要条件是 gcd(a,m)b\gcd(a, m) \mid b

高次同余方程