数论笔记
Dirt、
·
·
个人记录
数论笔记
质数
根据质数的定义，质数只会是1和它本身的倍数。
埃氏筛的思想，就是将每个数的倍数都标记为合数。
每个合数至少存在一个质因子，因此只需要在当前数为质数的时候标记其倍数即可。
复杂度 O(nloglogn) 。
v[0]=v[1]=true;
for(int i=2;i<=n;i++)
if(!v[i])
{
for(int j=i+i;j<=n;j+=i)
v[j]=true;
}
在欧拉筛中，每个数只会被其最小的质因子筛掉。
复杂度 O(n) 。
v[0]=v[1]=true;
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!v[i]) prime[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
{
v[i*prime[j]]=true;
if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
else
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
// i%prime[j]==0 即代表 i 被 prime[j] 筛过
// i 乘上其他的质数也是 prime[j] 的倍数
// 而每个数都只会被其最小的质因子筛掉
// 所以此时后面的数一定会被prime[j]筛掉，可以直接break
}
}
欧拉筛可以求积性函数的值，例如下文提到的欧拉函数。
欧拉函数，即 \varphi(n) ，表示小于等于 n 且与 n 互质的数的个数。
设 n = \prod \limits_{i=1}^n p_i^{k_i} ， p_i 为质数，则 \varphi(n) = n \times \prod \limits_{i=1}^n \frac{p_i-1}{p_i} 。
积性函数：函数 f(x) 为积性函数，则对于两个数 a,b，若 gcd(a,b) = 1 ，则有 f(ab) = f(a) \times f(b) 。
欧拉函数是积性函数。
根据这个性质，可以用欧拉筛来递推求欧拉函数的值。
对于一个数 n，如果 n 为质数，显然 \varphi(n) = n-1 。
如果 n 为合数，根据欧拉筛的过程， n 会被最小的质因子 p_1 筛掉。不妨设 n' = \frac{n}{p_1} 。
观察线性筛的过程，我们可以对 n' \bmod p_1 分类讨论：
若 n' \bmod p_1 = 0 ，则 n' 包含 n 的所有质因子。
此时有
\varphi(n) = n \times \prod \limits_{i=1}^n \frac{p_i-1}{p_i}
= p_1 \times n' \times \prod \limits_{i=1}^n \frac{p_i-1}{p_i}
= p_1 \times \varphi(n')
若 n' \bmod p_1 \ne 0 ，此时根据欧拉筛的性质， n' 与 n 互质。根据欧拉函数性质，有
\varphi(n) = \varphi(p_1) \times \varphi(n')
= (p_1 - 1) \times \varphi(n')
最大公约数
最大公约数：
多个数的最大公约数：
$gcd(a,b,c) = gcd(gcd(a,b),c)$ 。
维护当前最大公约数 $d$ ，对于每个数更新 $d$ 即可。
最小公倍数：
$lcm(a,b) = \frac{a \times b}{gcd(a,b)}$ 。
多个数的最小公倍数：
$lcm(a,b,c) = lcm(lcm(a,b),c)$ 。
按照与求 $gcd$ 相同的思路更新即可。
```cpp
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
```
- **裴蜀定理**
对于方程 $ax + by = c$ ， $x,y$ 有整数解的充要条件为 $gcd(a,b) \mid c$ 。
- **扩展欧几里得(Exgcd)**
用于求方程 $ax + by = gcd(a,b)$ 的一组可行解。
设
$ax_1 + by_1 = gcd(a,b)
bx_2 + (a \bmod b)y_2 = gcd(b,a \bmod b)
由欧几里得定理可知： gcd(a,b) = gcd(b,a \bmod b)。
\therefore ax_1 + by_1 = bx_2 + (a \bmod b)y_2
即 ax_1 + by_1 = bx_2 + (a - \left\lfloor \frac{a}{b} \right \rfloor \times b)y_2
即 ax_1 + by_1 = ay_2 + b(x_2 - \left\lfloor \frac{a}{b} \right \rfloor y_2)
将 $x,y$不断递归求解直至$b = 0$。当 $b = 0$ 时，即 $ax = a$，此时令 $x = 1,y = 0$ 并返回，每一层代入计算 $x,y$ 即可。
```cpp
void exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b,x,y);
int k=x;
x=y;
y=k-a/b*y;
}
```
### 同余
- **费马小定理**
若 $p$ 为素数，$ gcd(a,p) = 1$ ，则 $a^{p-1} \equiv 1 \pmod {p}$ 。
- **欧拉定理**
若$gcd(a,m) = 1$，则 $a^{ \varphi(m) } \equiv 1 \pmod {m}$ 。
费马小定理是欧拉定理在模数为质数时的特殊形式。
- **扩展欧拉定理**
$ a^{b} \equiv \begin{cases} a^{b \bmod \varphi(m)},gcd(a,m) = 1\\ a^{b}, gcd(a,m) \ne 1 , b < \varphi(m) \\ a^{b \bmod \varphi(m) + \varphi(m)},gcd(a,p) \ne 1 ,b \geqslant \varphi(m) \end{cases} \pmod {m}
形如 ax \equiv b \pmod {c} 的方程称为线性同余方程。
定理1：
方程 ax + by = c 与 ax \equiv c \pmod {b} 等价。有整数解的充要条件为 gcd(a,b) \mid c。
根据该定理，可以使用exgcd求出方程 ax + by = gcd(a,b) 的一组可行解 x_0,y_0 ，然后两边同时除以 gcd(a,b)，再乘 c，得到方程 acx_0/gcd(a,b) + bcy_0/gcd(a,b) = c，这样就找到了方程的一个解。
定理2：
若 x_0,y_0 为方程 ax + by = c 的一组解，则该方程的任意解可表示为 x = x_0 + \frac{b}{gcd(a,b)}k , y = y_0 - \frac{a}{gcd(a,b)}k, k \in Z 。
根据该定理，可以求出方程的所有解。令 t = b / gcd(a,b) ，则最小整数解 x = （x_0 \bmod t + t) \bmod t 。
排列组合
从 n 个不同元素中任取 m 个元素按照一定顺序排成一列，叫做从从 n 个不同元素中取出 m 个元素的一个排列。
从 n 个不同元素中取出 m 个元素的所有排列个数，叫做从 n 个不同元素中任取 m 个元素的排列数，即 A_{n}^{m} / P_{n}^{m} 。
A_{n}^{m} = \frac{n!}{(n-m)!}
特别地，当 m>n 时， A_{n}^{m} =0 。
从 n 个不同元素中任取 m 个元素组成一个集合，叫做从 n 个不同元素中取出 m 个元素的一个组合。
从 n 个不同元素中取出 m 个元素的所有组合个数，叫做从 n 个不同元素中取出 m 个元素的组合数，即 C_{n}^{m} 。
C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}
特别地，当 m>n 时， C_{n}^{m} =0 。
组合数也常用 \dbinom{n}{m} 表示， C_n^m = \dbinom{n}{m} 。
组合数性质：
C_n^m = C_n^{n-m}
C_n^m = \frac{n}{m}C_{n-1}^{m-1}
C_n^m = C_{n-1}^m + C_{n-1}^{m-1}
\sum_{i=0}^n C_n^i = 2^n
待填坑......
咕咕咕
特别鸣谢：OIWIki （提供了本文中大部分内容）