数论

猿柒

8个月前更新

120

数论基础

整除

只在整数域上讨论。

一般形式为 $a|b$ ，叫做 $a$ 能整除 $b$。

其性质在此不过多叙述。

约数

与整除相关。若 $a|b$ ，则称 $b$ 是 $a$ 的倍数，$a$ 是 $b$ 的约数。

在具体问题中，如果没有特别说明，约数总是指正约数 。

最大公因数和最小公倍数

即 $(a,b)$ 与 $[a,b]$ ，有 $(a)[a]=a$ 的性质。

最大公约数有如下性质：

$(a_1,\dots,a_n)=(|a_1|,\dots,|a_n|)$
$(a,b)=(b,a)$
若 $a\ne 0$，则 $(a,0)=(a,a)=|a|$
$(bq+r,b)=(r,b)]$
$(a_1,\dots,a_n)=((a_1,a_2),a_3,\dots,a_n)$。进而 $\forall 1<k<n-1,~(a_1,\dots,a_n)=((a_1,\dots,a_k),(a_{k+1},\dots,a_n))$
对不全为 $0$ 的整数 $a_1,\dots,a_n$ 和非零整数 $m$，$(ma_1,\dots,ma_n)=|m|(a_1,\dots,a_n)$
对不全为 $0$ 的整数 $a_1,\dots,a_n$，若 $(a_1,\dots,a_n)=d$，则 $(a_1/d,\dots,a_n/d)=1$
$(a^n,b^n)=(a,b)^n$

最小公倍数有如下性质：

$[a_1,\dots,a_n]=[|a_1|,\dots,|a_n|]$
$[a,b]=[b,a]$
若 $a\ne 0$，则 $[a,1]=[a,a]=|a|$
若 $a\mid b$，则 $[a,b]=|b|$
$[a_1,\dots,a_n]=[[a_1,a_2],a_3,\dots,a_n]$。进而 $\forall 1<k<n-1,~[a_1,\dots,a_n]=[[a_1,\dots,a_k],[a_{k+1},\dots,a_n]]$
若 $a_i\mid m,~\forall 1\leq i\leq n$，则 $[a_1,\dots,a_n]\mid m$
$[ma_1,\dots,ma_n]=|m|[a_1,\dots,a_n]$
$[a,b,c][ab,ba,ca]=[a,b][b,c][c,a]$
$[a^n,b^n]=[a,b]^n$

最大公约数和最小公倍数可以组合出很多奇妙的等式，如：

$(a,b)[a,b]=|ab|$
$(ab,bc,ca)[a,b,c]=|abc|$
$\dfrac{(a,b,c)^2}{(a,b)(b,c)(a,c)}=\dfrac{[a,b,c]^2}{[a,b][b,c][a,c]}$

$ex$：一些作者认为 $0$ 和 $0$ 的最大公约数无定义，其余作者一般将其视为 $0$。C++ STL 的实现中采用后者，即认为 $0$ 和 $0$ 的最大公约数为 $0$。

互素

若 $(a_1,a_2)=1$，则称 $a_1$ 和 $a_2$ 互素（既约）。

多个整数互素，不一定两两互素。例如 $6$、$10$ 和 $15$ 互素，但是任意两个都不互素。

素数

若一整数 $p \ne 0,\pm1$ 满足 $p$ 除了 $1$ 和它本身的约数外没有其他约数，则称这个数为约数，反之即为和数。

算术基本引理

通过素数的性质我们可得：

若 $p$ 为素数，且 $p|a_1a_2$，那么 $p|a_1$ 或 $p|a_2$ 成立。

算术基本定理（唯一分解定理）

设一正整数 $a$，必有：

\[a=p_1^{k_1}p_2^{k_2}…p_n^{k_n} ,p_1<p_2<…<p_n \]

这样的形式称作 $a$ 的标准素因数分解式。

同余

即除以某数的余数相同。

记为同余式：$a\equiv b \pmod p$

$ex$：若没有特殊说明，模数总是正整数。

性质：

同余是等价关系，即同余具有
- 自反性：$a\equiv a\pmod m$。
- 对称性：若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$。
- 传递性：若 $a\equiv b\pmod m,b\equiv c\pmod m$，则 $a\equiv c\pmod m$。
线性运算：若$a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$，则有：
- $a\pm c\equiv b\pm d\pmod m$。
- $a\times c\equiv b\times d\pmod m$。

积性函数

定义：若 $F(xy)=F(x)F(y),\gcd(a,b)=1$，则称函数 $F(x)$ 为积性函数。

欧拉函数 $\varphi(x)$ 就是典型的积性函数。

$ex$：若当 $\gcd(a,b)\ne 1$ 时仍有 $F(xy)=F(x)F(y)$，则称$F(x)$ 为完全积性函数。

筛法

埃拉托斯特尼筛法（埃氏筛）

过程

考虑这样一件事情：对于任意一个大于 $1$ 的正整数，那么它的 $x$ 倍就是合数（$x 1$ ）。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

vector<intprime;
bool is_prime[N];
void Eratosthenes(int n) {
    is_prime[0]=is_prime[1]=0;
    for(int i=2;i<=n;++i) is_prime[i]=true;
    for(int i=2;i<=n;++i){
        if (is_prime[i]){
            prime.push_back(i);
            if((long long)i*i>n) continue;
            for(int j=i*i;j<=n;j+=i) is_prime[j]=false;
        }
    }
}

时间复杂度为 $O(n\log \log n)$，已经很接近线性了。其实还可以只对前一半进行筛法，结合只筛奇数以及位运算的知识，可以把复杂度降为 $O(n)$，若是再加上分块，可变为 $O(\sqrt{n}+S)$，$S$ 为一常数。

线性筛（欧拉筛）

我们每次对于一个数，只选择其最小质因子进行标记，当 $i \bmod pri[j]=0$ 时意味着这已经有更小的数标记过当前数，所以退出循环。

int pri[1000010];
bool isp[N],cnt=0;
void prime(int n){
    memset(isp,1,sizeof(isp));
    isp[1]=0;
    for(int i=2;i<=n;++i){
        if(isp[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt && i*pri[j]<=n;++j){
            isp[i*pri[j]]=0;
            if(i%pri[j]==0) break;
        }
    }
}

这样优化，时间复杂度降为 $O(n)$。

拓展

筛法可以处理欧拉函数 $\varphi(n)$，只需再添几行代码：

int pri[1000010];
bool isp[N],cnt=0;
int phi[1000010];
void prime(int n){
    memset(isp,1,sizeof(isp));
    isp[1]=0;
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(isp[i]) pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt && i*pri[j]<=n;++j){
            isp[i*pri[j]]=0;
            if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
}

逆元

定义 $ax \equiv 1 \pmod b$，则称 $x$ 为 $a$ 在模 $b$ 意义下的逆元。记作 $a^{-1}$。

求法

拓展欧几里得法

void exgcd(int a, int b, int& x, int& y) {
  	if (b == 0) {
    	x = 1, y = 0;
    	return;
  	}
  	exgcd(b, a % b, y, x);
  	y -= a / b * x;
}

本质上是一个原理。

快速幂法

因为有 $a^{p-1}\equiv 1 \pmod p$，所以有 $a^{p-2}a \equiv 1 \pmod p$，所以 $a^{p-2}$ 即为逆元。

int qpow(long long a, int b) {
  	int ans = 1;
  	a = (a % p + p) % p;
  	for (; b; b >>= 1) {
    	if (b & 1) ans = (a * ans) % p;
    	a = (a * a) % p;
  	}
  	return ans;
}

线性求法（不会证，自己搜）

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

中国剩余定理（CRT）

可求解如下形式的一元线性同余方程组（其中 $n_1, n_2, \cdots, n_k$ 两两互质）：

$\begin{cases} x &\equiv a_1 \pmod {n_1} \ x &\equiv a_2 \pmod {n_2} \ &\vdots \ x &\equiv a_k \pmod {n_k} \ \end{cases} $

上面的「物不知数」问题就是一元线性同余方程组的一个实例。

过程

计算所有模数的积 $n$；
对于第 $i$ 个方程：
1. 计算 $m_i=\frac{n}{n_i}$；
2. 计算 $m_i$ 在模 $[n_i$ 意义下的逆元 $m_i^{-1}$；
3. 计算 $c_i=m_im_i^{-1}$（不要对 $n_i$ 取模）。
方程组在模 $n$ 意义下的唯一解为：$x=\sum_{i=1}^k a_ic_i \pmod n$。

LL CRT(int k, LL* a, LL* r) {
  	LL n = 1, ans = 0;
  	for (int i = 1; i <= k; i++) n = n * r[i];
  	for (int i = 1; i <= k; i++) {
    	LL m = n / r[i], b, y;
    	exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    	ans = (ans + a[i] * m * b % n) % n;
  	}
  	return (ans % n + n) % n;
}

来源链接：https://www.cnblogs.com/lizihan00787/p/18685868

评分

欢迎为Ta评分