数论

一些最最基本的数论知识(其实我一直不太会这些)

整除

若a可被b整除,记作$a\mid b$, 其中 $a\text{ 称为}b$ 的约数(因数)

整除的传递(?)性质：$a\mid b\wedge b\mid c⟹a\mid c$

平凡约数

对应非零整数a,平方约数为(正负)1和(正负)a

最大公约数与最小公倍数

欧几里得算法

用于计算两个数的最大公约数，即gcd(m,n)

也就是中学数学的辗转相除和根相减损法

求$0\le m<n$的最大公约数时使用如下递归式:

$$gcd(0,n)=n$$$$gcd(m,n)=gcd(n\mathrm{\%}m,m)$$$$gcd(m,n)=gcd(n-m,m)$$

除非m,n较为相近且较大,一般用辗转相除远快减法

最小公倍数

满足公式, 为了防止溢出通常先乘再除

$$lcm(m,n)=\frac{m\times n}{gcd(m,n)}$$

裴蜀定理

其实等价于exgcd

素数

互素

当$gcd(m,n)=1$时,我们说m,n互素

要注意的一点是多个数互素不意味着两两互素

素数判定

枚举到$\sqrt{n}$即可

py

def isPrime(a):
    if a < 2:
        return False
    for i in range(2, int(a**(1/2)) + 1):
        if a % i == 0:
            return False
    return True

数学基本定理

即唯一分解定理,对于正整数$a$必有:

$$a=p_1{p}_2{p}_3\cdots p_k$$

其中$p_i$为质数,且在不考虑顺序的情况下分解结果唯一

这是数学基本引理的等价形式,同样解释了素数的本质属性

分解质因数

朴素: 暴力枚举$[2,\sqrt{N}]$即可

Pollard Rho?不会

同余

a,b在模m意义下同余,记作:

$$a\equiv b\mid m$$

性质

• 传递性
• 加法乘法取模性质

线性同余方程

用exgcd或者逆元做即可

筛法与积性函数

根本不会