数论知识小结 [基础篇]

(latest updated on 2020.08.12)

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

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

$\sum$求和,$\prod$求积

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

$\lfloor x\rfloor $ 向下取整，$\lceil x\rceil $ 向上取整

$[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$

即$\begin{aligned} \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\end{aligned}$

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

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

性质:$\lfloor \frac{n} {ab}\rfloor =\lfloor \frac{\lfloor \frac{n} {a}\rfloor } {b}\rfloor $

数论分段：即对于$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$以内的素数个数用函数$\pi(n)=|prime\cap[1,n]|$表示，素数密度在渐进意义上是$O(\log n)$的

即可以认为$\pi(n)=O(\frac{n} {\log n})$(实际在$n$较小时完全看不出这一点)

$n$的唯一分解: $n=\prod_{p_i\in prime} p_i^{c_i}$

朴素的素数判别法:

一个显然方法的如果$x$不是质数，则$\exists y\in [2,\sqrt n] ,y|x$

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

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

朴素的质因数分解法:

即求$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$的部分，剩下的一个就知道了

1
2
3
4
5
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)$

更优化的只枚举质数作为因子，复杂度是$O(\pi(\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)$(实际我不会证明。。)

线性筛(欧拉筛)

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

直接上代码背板子好了

1
2
3
4
5
6
7
8
9
10
11
12
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$

复杂度分析：

首先是取模的分析，对于$\forall a,b,a\ge b$，必然满足$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)$

写成代码

1
2
3
4
5
6
7
8
9
10
// 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)$，证明这里略去

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)$质因数分解，然后可以

1.依次枚举每个因数判断是否有$a^i\mod n=1$，取最小的$i$，复杂度为$O(\sqrt n\log n)$

2.设$\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)$

1
2
3
4
5
6
7
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 溢出回来，$O(1)$但是很奇怪，通常不会挂

1
2
3
4
5
6
7
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;
}