数论知识小结 [基础篇]

Posted on 2023-08-12 Edited on 2024-04-19 In OI 笔记

数论知识小结 [基础篇]

符号 $(a,b)=\gcd(a,b)$。

乘除 $a|b\rightarrow b=ka (k\in \N^+)$。

$\sum$ 求和，$\prod$ 求积。

任意 $\forall$，存在 $\exists$。

$x$ 向下取整，$x$ 向上取整。

$[a,b]$ 区间，通常指整数即 $[a,b]\cap \Z$。

调和级数

数学上，调和级数为 $H_n=\sum_{i=1}^{n}\frac{1}{i}$。

在OI中，我们常用调和级数分析 $\sum_{i=1}^n\frac{n}{i}\approx n\ln n$。

把它近似看成是 $f(x)=\frac{n}{x}$ 在 $[1,n]$ 上的积分，它的原函数 $F(x)=n\ln x$。

即 $\displaystyle \sum_{i=1}^n\frac{n}{i}\approx \int_1^nf(x) dx=F(n)-F(1)=n\ln n-n\approx n\ln n$。

附：广义调和级数 $H^z_n=_{i=1}^{n} $ 它的无穷形式为黎曼函数 $\displaystyle \zeta(z)=H^{z}_{\infty}$。

向下取整的性质/数论分段

性质：$=$。

数论分段：即对于 $i=[1,n]$，把 $i$ 按照 $\lfloor \frac{n}{i}\rfloor$ 的值分成 $O(\sqrt n)$ 段，（ $2\cdot \sqrt n$ 段左右）。

证明：对于 $i\leq \sqrt n$，显然只有 $\sqrt n$ 个不同的值。

对于 $i>\sqrt n$，此时 $\frac{n}{i}<\sqrt n$，也只有 $\sqrt n$ 个不同的值。

素数/质数/质数密度

对于 $x>1$，若 $\nexists y\in[2,n-1],y|x$，则 $x$ 是一个质数，下文称素数集合为 $prime$ 集合。

用素数对于 $n$ 进行唯一分解 $n=\prod_{p_i\in prime} p_i^{c_i}$。

如果 $x$ 不是质数，则 $\exists y\in [2,\sqrt n] ,y|x$。

所以可以朴素写出一个 $O(\sqrt n)$ 的素数判别法。

$\pi(n)=|prime\cap[1,n]|$，素数密度在渐进意义上是 $O(\log n)$ 的，即在复杂度上可以认为 $\pi(n)=O(\frac{n}{\log n})$ （实际在 $n$ 较小时完全看不出这一点）。

利用这一点预先处理小素数，每次只判断素数，可以写出一个 $O(\frac{\sqrt n}{\log n})$ 的素数判别法。

更快的方法是 $\text{Miller Rabin}$，不要在这个时候学。

质因数分解：即求 $n=\prod p_i^{c_i},p_i\in prime$，其中 $\sum c_i\leq \log _2^n$。

由于对于一个数 $n$，最多存在一个 $y\in prime \cap [\sqrt n,n],y|n$，因此可以先分解掉 $y<\sqrt n$ 的部分，剩下的一个就知道了。

void Factor(int n){
    for(int i=2;i*i<=n;++i) if(n%i==0)  
        while(n%i==0) printf("%d ",i),n/=i; // 分解掉<sqrt(n)的部分
    if(n>1) printf("%d ",n); // 如果还剩下，那么就是>sqrt(n)的一个质数
}

复杂度是 $O(\sqrt n +\log n)$。

朴素的素数筛法：埃氏筛。

对于 $[2,n]$ 每个数 $i$，$x=ki(k>1)$ 均不是质数，直接枚举复杂度为调和级数 $O(n\ln n)$。

更优化的，对于 $[2,n]$ 中每个质数 $i$，$x=ki(k>1)$ 均不是质数，由于素数密度为 $O(\log n)$，所以可以近似认为是 $O(n\log \log n)$，实际要慢一些。

线性筛(欧拉筛)

筛素数知识一个基础，可以筛很多函数，尤其是适用于积性函数。

直接上代码背板子好了。

int notpri[N],prime[N],primecnt;
void Sieve(){
    notpri[1]=1;
    for(int i=2;i<=n;++i) {
        if(!notpri[i]) prime[++primecnt]=i;
        for(int j=1; j<=primecnt && 1ll*i*prime[j]<=n;++j){
            notpri[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

其中 $i\mod prime_j= 0$ 意味着后面的数已经被 $\frac{i}{prime_j}$ 筛掉了，所以可以 break。

复杂度是带有一定常数的 $O(n)$，还可以用来筛其他的一些函数。

$\gcd,\text{lcm}$

最大公因数 $\text{gcd(greatest common divisor)}$ 常用 $\gcd(x,y)=(x,y)$ 表示

最小公倍数 $\text{lcm(least common multiple)}$。

特别的：$(a,0)=a$。

求 $\gcd(a,b)$ 可以用辗转相除法（也称为欧几里得算法），即利用性质 $(a,b)=(a\mod b,b)$。

每次递归调用 $\gcd(b,a\mod b)$ 即可，边界为 $(a,0)=a$。

复杂度分析：

对于 $a\ge b\Rightarrow a\mod b \leq \frac{a}{2}$。

所以每次取模会减少一倍，复杂度为 $O(\log a)$。

附：扩展欧几里得算法

用于求解不定方程 $ax+by =1$ 的一组解 $(x,y)$。

存在解的条件是 $(a,b)=1$，否则 $(a,b)|ax+by$，即 $ax+by>1$。

用类似求 $\text{gcd}$ 的方法求出。

$ax+by=1$

$(a\mod b)\cdot x+ \lfloor \frac{a}{b}\rfloor\cdot b\cdot x + by=1$

$(a\mod b)\cdot x+ b\cdot (\lfloor \frac{a}{b}\rfloor\cdot x + y)=1$

那么如果求出 $(a\mod b)\cdot x'+b\cdot y'=1$ 的解。

则 $x'=x,y'=\lfloor \frac{a}{b}\rfloor \cdot x+y$。

即 $x=x',y=y'-\lfloor \frac{a}{b}\rfloor x$。

每次都递归求出 $(a\mod b) \cdot x+ by =1$。

复杂度与 $\gcd$ 相同，最后的 $(a,b)=a=1,b=0$ 是边界条件，此时 $x+0\cdot y=1$ 的一组解是 $(1,0)$。

写成代码

// ax + by =1
int Exgcd(int a,int b,int &x,int &y) {
    if(b==0){ 
        if(a!=1) return 0; // (a,b)!=1 ,不存在解
        x=1,y=0; // 初始解
        return 1;
    } 
    Exgcd(b,a%b,y,x),y-=a/b*x; // 带入上面的式子，注意这里带入的是(b,a%b),所以x,y要反过来
    return 1;
}

注意求出的 $x,y$ 不保证为正数

因数个数

似乎没有找到规范的函数定义，所以下称 $d(n)$。

即 $d(n)=|\{i|i\in[1,n]\and i|n\}|$。

对于 $n=\prod p_i^{c_i}$，列一条小学的公式 $d(n)=\prod (c_i+1)$。

因数个数一个非常松的上界是 $O(\sqrt n)$，证明这里略去。

实际上，搜索得到的上界大致是：

maxn=10^ 1  max= 4
maxn=10^ 2  max= 12
maxn=10^ 3  max= 32
maxn=10^ 4  max= 64
maxn=10^ 5  max= 128
maxn=10^ 6  max= 240
maxn=10^ 7  max= 448
maxn=10^ 8  max= 768
maxn=10^ 9  max= 1344
maxn=10^10  max= 2304
maxn=10^11  max= 4032
maxn=10^12  max= 6720
maxn=10^13  max= 10752
maxn=10^14  max= 17280
maxn=10^15  max= 26880
maxn=10^16  max= 41472
maxn=10^17  max= 64512
maxn=10^18  max= 103680

可以看到，因数个数是非常少的

附:

质因数个数 $\Omega(n)=|prime\cap [1,n]|$，非常松的上界是 $\Omega(n)=O(\log n)$。

约数和函数 $\sigma(n)=\sum_{i|n}i$。

费马小定理/欧拉定理/欧拉函数/阶

费马小定理：对于任意质数 $P,x>0,x^{p-1}\equiv 1 \pmod P$。

欧拉函数：$\varphi(n)$ 为 $[1,n-1]$ 中与 $n$ 互质的数个数，特别的 $\varphi(1)=1$。

设 $n=\prod p_i^{c_i}$ 其中 $p_i$ 是质数，$c_i>0$，则 $\varphi(n)=\prod p_i^{c_i-1}(p_i-1)=n\prod\frac{p_i-1}{p_i}$。

对于可以通过类似筛素数的方法求出来 $[1,n]$ 的 $\varphi(i)$。

对于数 $n$，需要采用质因数分解求出，朴素的做法为 $O(\sqrt n)$，用 $\text{Pollard's Rho}$ 算法复杂度更低。

欧拉定理：对于任意数 $P>1,x>0,x^{\varphi(P)}\equiv 1\pmod P$。

推论：$x^c\equiv x^{c\mod \varphi (P)} \pmod P$。

很显然，费马小定理是欧拉定理的特殊情况。

阶：对于 $(a,n)=1$ 的整数，满足 $a^r≡1 \pmod n$ 的最小整数 $r$，称为 $a$ 模 $n$ 的阶，以下记作 $d(a)$。

显然 $a^i \mod n$ 构成了一个以 $r$ 为最小正周期的循环。

性质：根据欧拉定理 $a^{\varphi(n)}\mod n=1$，所以有 $d(a)|\varphi(n)$ 。

求解阶：先对于 $\varphi(n)$ 质因数分解，然后可以。

依次枚举每个因数判断是否有 $a^i\mod n=1$，取最小的 $i$，复杂度为 $O(\sqrt n\log n)$。
设 $\varphi(n)=p_i^{c_i}$，令 $x=\varphi(P)$，从 $x$ 开始，如果 $a^{\frac{x}{p_i}}\mod n=1$，则 $x\rightarrow \frac{x}{p_i}$。

预处理复杂度受限于质因数分解（下文有介绍）。

单次查询复杂度上限是 $O(\log ^2 P)$ （为快速幂复杂度乘上 $\sum c_i$）。

模逆元（乘法逆元）

对于任意数 $x>1,P>1,(x,P)=1$，存在一个数 $\frac{1}{x}\equiv y\pmod P$。

即 $xy\equiv 1 \pmod P$， $y$ 为 $x$ 的一个模逆元。

当 $P$ 为质数时，由于 $x^{P-1}\equiv 1 \pmod P$，所以 $y\equiv x^{P-2}\pmod P$ 为 $x$ 的一个逆元。

当 $P$ 不为质数时，如果已知 $\varphi (P)$，可以类似得做，否则可以构造 $a\cdot x+b\cdot P=1$，用扩展欧几里得算法求出一组合法解 $(a,b)$，则$a$ 即为一个答案。

原根/指标

原根：一个数 $P$ 有原根的条件是他可以表示为 $P=1,2,4,p,2p,p^n(p\in prime)$。

对于 $P$，令 $d(x)$ 为 $x$ 模 $P$ 的原根，若存在 $d(x)=\varphi(P)$，则$x$ 是 $P$ 的一个原根。

找原根：

设 $\varphi(P)=\prod p_i^{c_i}$，其中 $p_i$ 是质数。

由于 $d(x)|\varphi(P)$，如果 $d(x)<\varphi(P)$ 那么必然存在一个$x^{\frac{\varphi(P)}{p_i}}\equiv 1\pmod P$。

所以先求一遍质因数分解，然后快速幂判断就可以做到 $O(\log ^2 P)$ 判断原根。

显然原根不唯一，已经被证明对于任意 $P$ 如果存在原根，则其最小原根不超过 $O(P^{\frac{1}{4}})$ 级别。

指标：

对于一个数 $P$ 和它的一个原根 $x$，对于 $\gcd(y,P)=1$，则 $y$ 一定可以用$x^i$ 表示，那么 $i$ 就是 $y$ 的指标。

同时，$y$ 模 $P$ 的阶就是 $d(y)=\frac{\varphi(P)}{\gcd(\varphi(P),i)}$，可以认为是数列 $a_j=i\cdot j\mod \varphi(P)$ 的周期问题。

可以使用 $\text{BSGS}$ 算法在 $O(\sqrt P\log P)$ 或者 $O(\sqrt P)$ 的时间内求出一个数的指标。

（关于去掉 $\log P$：只需要处理出模逆元直接累乘，每次用 $\text{Hash Table}$ 访问即可）。

指标在二次剩余的较劣做法中也有应用，同时也可以直接套用性质用于阶的求解

快速乘

求 $x,y\in[0,P-1],P\leq 10^{18},x\cdot y \mod P$。

直接乘法会爆 long long

可以用类似快速幂的方法写，复杂度为 $O(\log P)$。

typedef long long ll;
typedef unsigned long long ll;
void qmul(ll x,ll y,ll P){
    ll res=0;
    for(;y;y>>=1,x=(x+x)%P) if(y&1) res=(res+x)%P;
    return res;
}

另一种方法是强行用 long double 使得精度误差比较小。

然后计算的时候用 unsigned long long 溢出，溢出过程中只要差距不超过$2^{64}$ 就能保证准确。

复杂度为 $O(1)$，通常不会挂。

typedef long long ll;
typedef unsigned long long ll;
void qmul(ll x,ll y,ll P){
    ull z=(long double)x/P*y;
    ll res=(ull)x*y-(ull)z*P;
    return (res%P+P)%P; // ps : 通常偏差在 +-P 以内，因为实际上long double =精度误差非常小
}

数论知识小结 [基础篇]

调和级数

向下取整的性质/数论分段

素数/质数/质数密度

线性筛(欧拉筛)

\(\gcd,\text{lcm}\)

附：扩展欧几里得算法

因数个数

费马小定理/欧拉定理/欧拉函数/阶

模逆元（乘法逆元）

原根/指标

快速乘