基础数论

各种基础数论的合集

最大公约数(gcd)

我们常用欧几里得的辗转相除法求gcd
原理:$gcd(x,y)=gcd(x,y-x)$
代码实现:

1
2
3
4
int gcd(int x , int y)
{
return y == 0 ? x : gcd(y , x % y);
}


最小公倍数(lcm)

$$lcm(x , y) = x \times y / gcd(x , y)$$


扩欧

对于方程$ax + b y = c$ , 有解的充要条件是$gcd(a , b) | c$。
所以我们通常将方程除以$c/gcd(a,b)$,进行求解后,将x,y同乘$c/gcd(a,b)$
求解方程:$a x + b y = gcd(a , b)$:
1.$b = 0$ 时 ,
$x = 1 , y = 0$
2.$ab \not= 0$ 时 ,
设$a \times x_1 + b \times y_1 = gcd(a , b)$
$b \times x_2 + a \bmod b \times y_2 = gcd(b , a \bmod b)$
由于$a \bmod b = a - a / b \times b$
所以$b \times x_2 + (a - a / b \times b) \times y_2 = gcd(a , b)$
整理得:$a \times y_2 + b \times (x_2 - a / b \times y_2) = gcd(a,b)$
由于$gcd(a , b) = gcd(b , a \bmod b)$
根据恒等定理,得:
$x_1 = y_2$
$y_1 = x_2 - a / b \times y_2$
根据这个就可以求出方程的解了
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int exgcd(int a , int b , int &x , int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int ans = exgcd(b , a % b);
int t = x;
x = y;
y = t - a / b * y;
return ans;
}


求解线性同余方程

对于方程:$ax\equiv c\pmod b,$
其实它等价于$ax + by = c$
就可以按二元一次方程的求解方法求解
我们要研究的是解的最小间隔dis:
∵$ax\equiv c\pmod b$ , $dis$是解的间隔
∴$a(x+dis)\equiv c\pmod b$
∴$a\times dis≡0\pmod b$
即:$a \times dis \bmod b = 0$
∴$dis = b / gcd(a , b)$
所以同余方程的解为:
$x_i = (x_0 + i \times dis) mod b$
$i = 0 … gcd(a , b) - 1$
最小正整数解为
$(ans \bmod dis + dis) \bmod dis$


排列&组合

排列:从$n$个不同物体不重复地取出$m$个做排列的方案数,记作:$A_n^m$
组合:从$n$个不同物体不重复地选择$m$个做组合的方案数,记作:$C_n^m$
根据定义有:
$$A_n^m=\frac{n!}{(n-m)!}$$
$$C_n^m=\frac{n!}{(n-m)!\times m!}=C_n^{n-m}$$

一些常用公式

$$\sum_{i=0}^{n}C_n^i=2^n$$

常用$O(n^2)$递推公式:
$$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$$

(noip2016Day2T1我傻逼啊,那时候排列组合渣渣啊,对这个式子一无所知,爆掉啦,%%%抄作业大神AK)
震惊!组合数与杨辉三角有XX,原因竟然是这个……

$$C_{n+m+1}^{m}=C_{n+m}^{m}+C_{n+m-1}^{m-1}+\cdots +C_{n+1}^{1}+C_{n}^{0}$$

$$C_{n}^{m} \times C_{m}^{r} = C_{n}^{r} \times C_{n-r}^{m-r}$$


特殊排列&组合

物体间不全相异的排列数

$$\frac{n!}{n_1!\times n_2!\times\cdots\times n_k!}$$
($n_1$~$n_k$表示每种物体的数量)

重复组合

从$n$个不同物体中选$r$个物体,允许重复选择,不考虑次序地把这$r$个物体组合成一组,称为重复组合。
$$Ans=C_{n+r-1}^{r}$$

理解:隔板法

n个球,用r个隔板隔开,隔板之后的物体代表选中的物体,求球和隔板的组合数(但最后一个物体不能是隔板,所以是n-1个球,r个隔板,最后加一个球),在根据物体间不全相异的排列数公式,得到$\frac{(n+r-1)!}{(n-1)!r!}$,即$C_{n+r-1}^{r}$
(讲的时候没有太听懂,后来补的,不大记得讲的时候是怎样”隔板”的,似乎没有这么复杂,但这样是解释的通的,应该是这样的吧)


约数和定理

令$$n=\prod_{i=1}^{k}p_i^{a_i}$$
其中$p_{i}$为$n$的质因数。
则$n$的所有正约数和为:
$$f(n)=\prod_{i=1}^{k}(\sum_{j=0}^{a_i} p_i^j)$$


卡特兰数

$$C_{0}=1$$
$$C_{n}=\sum_{i=0}^{n - 1} C_{i}\times C_{n - i - 1}$$

常见模型

1.平面直角坐标系中只能向上向右走,且不能穿过y=x,求走法总数
2.求长度为n的括号序列总数
3.出栈顺序
3.节点为n的不同二叉树数目


康托展开

康托展开表示的是当前排列在n个不同元素的全排列中的名次
康托展开为:
$$ans = a_n \times (n - 1)! + a_{n-1}\times (n - 2)! + … + a_1 \times 0!$$
$a_i$表示第$i$个元素在第$i$至第$n$个元素中排列第几
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
LL Cantor()
{
LL tmp , ans = 0;
For(i , 1 , n)
{
tmp = 0;
For(j , i + 1 , n)
if (a[i] > a[j])
++ tmp;
ans += tmp * xp[n - i];
}
return ans;
}

逆康托展开

辗转相除法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void unCantor(LL ct)
{
vector <int> vct;
LL x , y;
-- ct; //因为康托展开是从0开始的!!!
For(i , 1 , n)
vct.pb(i);
Fordown(i , n , 1)
{
x = ct / xp[i - 1];
y = ct % xp[i - 1];
ct = y;
sort(vct.begin() , vct.end());
Ans[n - i + 1] = vct[x];
vct.erase(vct.begin() + x);
}
}


逆元

对于正整数和,如果有$ax≡1\pmod m$,那么把这个同余方程中的最小正整数解叫做$a$模$m$的逆元。

费马小定理

$a^{p-1}≡1\pmod p$
两边同除以a
$a^{p-2} ≡1/a \pmod p$
$1/a$即$inv(a)$
所以$inv(a) = a^(p-2) \pmod p$
用快速幂求一下,复杂度$O(log_2n)$

扩展欧几里德算法

还记得扩展欧几里德吗?(不记得的话,欧几里得会伤心的)
$ax + by = 1$
解的$x$就是$a$关于$b$的逆元
$y$就是$b$关于$a$的逆元

线性递推

p是个质数的时候有
$$inv(a) = (p - \lfloor p / a\rfloor) \times inv(p \bmod a) \bmod p$$
证明:
设$x = p \bmod a,y =\lfloor p / a\rfloor$
于是有 $x + y \times a = p$
$(x + y \times a) \bmod p = 0$
移项得 $x \bmod p = -y \times a \bmod p$
$x \times inv(a) \bmod p = (-y) \bmod p$
$inv(a) = (p - y) \times inv(x) \bmod p$
于是 $inv(a) = (p - p / a) \times inv(p \bmod a) \bmod p$


素数

推荐(xiao)一波本人讲解关于素数的博客:
click me

整数的唯一分解定理

$A=p_1^{k_1}\times p_2^{k_2}\times\cdots\times p_n^{k_n}$
($p_i$为质数)

威尔逊定理

当$p$为素数时,$(p-1)!≡-1 \pmod p$
其逆定理:
若对某一正整数$p$,存在$(p-1)\not\equiv -1(mod p)$,则p一定为素数
费马小定理
假如$p$是素数,$a$为正整数,$(a,p)=1$,那么$a^{p-1}\equiv 1\pmod p$

Contents
  1. 1. 最大公约数(gcd)
  2. 2. 最小公倍数(lcm)
  3. 3. 扩欧
  4. 4. 求解线性同余方程
  5. 5. 排列&组合
    1. 5.1. 一些常用公式
  6. 6. 特殊排列&组合
    1. 6.1. 物体间不全相异的排列数
    2. 6.2. 重复组合
      1. 6.2.1. 理解:隔板法
  7. 7. 约数和定理
  8. 8. 卡特兰数
    1. 8.1. 常见模型
  9. 9. 康托展开
  10. 10. 逆康托展开
  11. 11. 逆元
    1. 11.1. 费马小定理
    2. 11.2. 扩展欧几里德算法
    3. 11.3. 线性递推
  12. 12. 素数
    1. 12.1. 整数的唯一分解定理
    2. 12.2. 威尔逊定理