扩展欧几里得算法(ExGCD)代码

之前的数学笔记中讲过这个算法,所以这里把代码贴一下。

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

OI数学专题笔记 - 2

素数的定义和判定

定义

如果 pp 只有 1 和 pp 两个印子,则 pp 为负数。

Miller-Rabin 素性测试

如果 nn 为素数,取 a<na < n ,设 n1=d×2rn - 1 = d \times 2^r ,则要么 ad1(modn)a^d \equiv 1 \pmod n ,要么 0i<r,s.t.ad×2i1(modn)\exists 0 \leq i < r, s.t. a^{d \times 2^i} \equiv -1 \pmod n 。(费马小定理的推广形式)

阅读全文 »

矩阵快速幂学习笔记

快速幂

对于计算 xyx^y 只需要计算 xy2×xy2x^{\frac{y}{2}} \times x^{\frac{y}{2}} ,如果 yy 是奇数只需要再乘 xx ,这样就可以把 O(n)O(n) 的时间复杂度降为 O(logn)O(logn)

阅读全文 »

高斯消元

基本高斯消元法

对于行列式:

a11a12a13...a1na21a22a23...a2na31a32a33...a3n...............an1an2an3...ann\left | \begin{array}{cccc} a_{1 1} & a_{1 2} & a_{1 3} & ... & a_{1 n} \\ a_{2 1} & a_{2 2} & a_{2 3} & ... & a_{2 n} \\ a_{3 1} & a_{3 2} & a_{3 3} & ... & a_{3 n} \\ ... & ... & ... & ... & ... \\ a_{n 1} & a_{n 2} & a_{n 3} & ... & a_{n n} \end{array} \right |

阅读全文 »

OI数学专题笔记 - 1

排列和逆序对

定义

  • 以任意一种顺序将相异的 nn 个数重排,每个顺序都称作一个排列。

  • 在排列 a1a2..ana_1 a_2 .. a_n 中,如果每有一个二元组 (i,j)(i, j) 满足 i<ji < jai>aja_i > a_j ,则称 ai,aja_i, a_j 组成了一个逆序对。

  • 排列 a1a2...ana_1 a_2 ... a_n 的逆序数表示为 τ(a1a2...an)\tau(a_1 a_2 ... a_n)

  • 定义:如果一个排列的逆序数为偶数,则称此排列为偶排列,否则称为奇排列。

  • 定义:在一个排列中,对换其中某两个数,其余的数不动,得到另一个排列,这种操作称为一个对换。

阅读全文 »

线段树学习笔记

概述

假设要从数组arr[0 ... n - 1]查找某个数组某段区间的最小值,其中数组大小固定,但是数组中的元素可以随时更新。一个简单的解法是遍历数组区间寻找最小值,时间复杂度是O(n)O(n),额外空间复杂度O(1)O(1),当数据量特别大,查询操作很频繁时,耗时可能不能够满足要求。

阅读全文 »

SPFA学习笔记

介绍

SPFA(Shortest Path Faster Algorithm)就是队列优化的Bellman-Ford,时间复杂度声称可以优化到O(km)O(km),实际很容易卡到最坏的情况O(nm)O(nm),可以处理负权边,判定负权环。建议除非有负权边,否则不要用SPFA。

阅读全文 »

Dijkstra学习笔记

介绍

这个算法适用于非负权图中求单源最短路(一个顶点到其他所有顶点的最短路),有着稳定优秀的时间复杂度,暴力Dij时间复杂度为O(n2)O(n^2),堆优后为O(mlogn)O(mlogn)。事实上mmn2n^2是同阶的,不过一般情况下mm远小于n2n^2,这种图被称为稀疏图;而mm相对较大的图则被称为稠密图,这种情况下暴力Dij可能要比堆优Dij更优。

阅读全文 »