目录
  1. 1. 写在前面
  2. 2. 常用C++STL(模板)合集
    1. 2.1. 万能(误)算法头文件(部分)
    2. 2.2. 动态数组(vector)、双向链表(list)
    3. 2.3. 普通队列、双端队列、优先队列
    4. 2.4.
    5. 2.5. pair(成组)、set(有序元素序列)
    6. 2.6. map(映射)
    7. 2.7. 一些C++的功能/特性
    8. 2.8. 强大的pb_ds库
  3. 3. 数据结构部分
    1. 3.1. 单调队列
    2. 3.2. 单调栈
    3. 3.3. 归并排序、逆序对数
    4. 3.4. 线段树/树状数组
    5. 3.5. 可持久化线段树(主席树)
      1. 3.5.1. 朴素版本
      2. 3.5.2. 简约版本
    6. 3.6. 归并树(划分树)
    7. 3.7. ST表(倍增)求区间最值
      1. 3.7.1. 一维
      2. 3.7.2. 二维
    8. 3.8. 字典树
    9. 3.9. 树链剖分
      1. 3.9.1. 点权
      2. 3.9.2. 边权
    10. 3.10. 并查集
      1. 3.10.1. 普通并查集
      2. 3.10.2. 带权并查集
  4. 4. 数论部分
    1. 4.1. 一些基础的公式、定理
    2. 4.2. 因数、余数、质数基础
      1. 4.2.1. 埃氏素数筛法
      2. 4.2.2. 欧拉函数
      3. 4.2.3. 欧几里得定理求a、b最大公因数、最小公倍数
      4. 4.2.4. 扩展欧几里得
      5. 4.2.5. 线性同余方程
      6. 4.2.6. 模线性方程组求解(中国剩余定理)
      7. 4.2.7. 乘法逆元
      8. 4.2.8. 二次剩余
      9. 4.2.9. 普通分解质因数
    3. 4.3. 约数的和取余
    4. 4.4. 组合数相关
      1. 4.4.1. 一些定理
      2. 4.4.2. 预处理组合数
      3. 4.4.3. 求单个组合数
      4. 4.4.4. 卢卡斯定理
      5. 4.4.5. 斯特林数
    5. 4.5. Miller_Rabin 快速大素数测试
    6. 4.6. Pollard_rho大数分解质因数
    7. 4.7. 欧拉降幂公式
    8. 4.8. BSGS大步小步算法
    9. 4.9. 莫比乌斯函数、反演
    10. 4.10. 牛顿迭代法求平方根
    11. 4.11. 高斯消元
    12. 4.12. 线性基
    13. 4.13. 斐波那契数列
  5. 5. 图论部分
    1. 5.1. 邻接表存图
    2. 5.2. Vector伪邻接表存图
    3. 5.3. Dijkstra单源最短路
    4. 5.4. SPFA单源最短路
    5. 5.5. Floyd多源最短路
    6. 5.6. 最小生成树MST
      1. 5.6.1. Kruskal
      2. 5.6.2. Prim
    7. 5.7. 最近公共祖先(LCA)
    8. 5.8. 二分图匹配
    9. 5.9. 网络流
    10. 5.10. 树分治(点分治)
  6. 6. 字符串处理部分
    1. 6.1. KMP
    2. 6.2. exKMP
  7. 7. 博弈论部分
    1. 7.1. nim博弈
    2. 7.2. Bash博弈
    3. 7.3. Wythoff博弈
    4. 7.4. 斐波那契博弈
    5. 7.5. 环形博弈
    6. 7.6. SG函数
  8. 8. 动态规划部分
    1. 8.1. 背包
    2. 8.2. 区间DP
  9. 9. 计算几何部分
    1. 9.1. Kuangbin几何模板
  10. 10. 杂项
    1. 10.1. 竞赛常用快速读入骚操作
    2. 10.2. C++高精度模板
    3. 10.3. Java大整数
    4. 10.4. Java大实数
    5. 10.5. 手动扩栈
    6. 10.6. 对拍
个人模板整理

写在前面

本篇博客主要用于本人的ICPC比赛用模板整理,方便查阅。

如有网友发现哪里写的不好、哪里可以改进,欢迎提出。

持续更新中…

常用C++STL(模板)合集

注意:C++STL全部需要使用命名空间std

  • 万能(误)算法头文件(部分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
using namespace std;
int main() {
iterator begin, end; // 指代某种数据结构首尾迭代器
T i, x, a, b;

sort(begin, end, <cmp>); // 排序函数,默认从小到大
// 遇到需要特殊排序的需要编写cmp函数 or 重载内部运算符
next_permutation(begin, end); // 下一个排列
prev_permutation(begin, end); // 前一个排列

set_union(begin(a), end(a), begin(b), end(b), begin(c));
// 取两个有序序列a、b的并集,存放到c中
set_intersection(begin(a), end(a), begin(b), end(b), begin(c));
// 取两个有序序列a、b的交集,存放到c中
set_difference(begin(a), end(a), begin(b), end(b), begin(c));
// 取两个有序序列a、b的差集,存放到c中
unique(begin, end); // 有序数据去重
merge(begin(a), end(a), begin(b), end(b), begin(c), cmp);
// 合并两个有序序列a、b,存放到c中,cmp可定义新序列排列方式

lower_bound(begin, end, x); // 返回x的前驱迭代器
// 在普通的升序序列中,x的前驱指的是第一个大于等于x的值
upper_bound(begin, end, x); // 返回x的后继迭代器
// 在普通的升序序列中,x的后继指的是第一个大于x的值
// 上述两个函数时间复杂度为O(log2(n)),内部实现是二分
// 如果找不到这样的值,会返回end

find(begin, end, x); // O(n)查找x
binary_search(begin, end, x) // 二分查找x,返回bool
min(a, b); max(a, b); // 返回a、b中的最小/最大值
fill(begin, end, x); // 往容器的[begin, end)内填充x
swap(a, b); // 交换a、b的值

return 0;
}
  • 动态数组(vector)、双向链表(list)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <vector>
#include <list>
using namespace std;
int main() {
T i;
unsigned int n, x;
bool flag;
iterator it;

// 动态数组部分
// 注意vector的空间需要预留两倍大小
vector<T> v;
v.push_back(i); // 往数组尾添加一个元素i
v[x]; // 访问第x - 1个元素
v.begin(); // 返回头元素的迭代器
v.end(); // 返回末尾迭代器(尾元素的下一个)
n = v.size(); // 数组中元素数量
v.pop_back(); // 删除最后一个元素
v.erase(it); // 删除某个的元素
v.insert(x, i); // 在x位置插入元素i
// erase、insert时间复杂度为O(n)
v.clear(); // 清空数组,不释放空间
flag = v.empty(); // 判断数组是否为空(真值)

// 链表部分
list<T> li;
li.push_front(i); // 在链头添加一个元素i
li.push_back(i); // 在链尾添加一个元素i
li.pop_front(i); // 删除链表头元素
li.pop_back(i); // 删除链表尾元素
li.erase(it); // 删除某个的元素
li.insert(x, i); // 在x位置插入元素i O(n)
li.begin(); // 返回头元素的迭代器
li.end(); // 返回末尾迭代器(尾元素的下一个)
n = li.size(); // 链表中元素数量
li.remove(i); // 删除链表中所有值为i的元素
li.unique(); // 移除所有连续相同元素,留下一个
li.reverse(); // 反转链表
li.clear(); // 情况链表,不释放空间

return 0;
}
  • 普通队列、双端队列、优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <queue> // 队列头文件
#include <deque> // 双端队列头文件
using namespace std;
int main() {
T i;
unsigned int n, x;
bool flag;

// 普通队列部分,注意queue没有迭代器
queue<T> q, tmp_q; // 定义普通队列
q.push(i); // 队尾插入元素i
q.pop(); // 弹出队首元素
i = q.front(); // 访问队首元素
i = q.back(); // 访问队尾元素
n = q,size(); // 队内元素数量
flag = q.empty(); // 判断队列是否为空(真值)
q.swap(tmp_q); // 交换两个队列元素

// 优先队列部分,注意其没有迭代器
priority_queue<T> pq; // 定义优先队列
pq.push(i); // 队尾插入元素i
pq.pop(); // 弹出队首元素
i = pq.top(); // 访问队首元素
n = q,size(); // 队内元素数量
flag = q.empty(); // 判断队列是否为空(真值)
q.swap(tmp_q); // 交换两个队列元素
// 注意优先队列内部是使用<运算符,默认大根堆
// 可以采用重载运算符或加入运算符类自定义排列方式
// 例:priority_queue<T, vector<T>, greater<T> > 小根堆
/*
struct node {
int x, y;
};
bool operator < (node a, node b) {
// 这里注意是<右边的元素会放在前面
if(a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
priority_queue<node>
*/

// 双端队列部分
// 注意deque用到了map来映射,时间复杂度上常数略大
deque<T> dq; // 定义双端队列
// 可以称为vector、list、queue的结合体
// 用法类似,这里只给代码不做注释
dq.push_back(i);
dq.push_front(i);
dq.front();
dq.back();
dq.pop_front();
dq.pop_back();
dq.begin();
dq.end();
dq[x];
n = dq.size();
flag = dq.empty();
dq.insert(x, i);

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stack>
using namespace std;
int main() {
T i;
unsigned int n;
bool flag;

stack<T> st; // 注意stack没有迭代器
st.push(i); // 往栈顶加入一个元素
st.pop(); // 弹出栈顶元素
i = st.top(); // 获得栈顶元素的值
flag = st.empty(); // 判断是否为空(真值)
n = st.size(); // 获得栈内元素个数

return 0;
}
  • pair(成组)、set(有序元素序列)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <set>
#include <pair>
using namespace std;
int main() {
T i;
T1 t1;
T2 t2;
iterator it;
unsigned int n;
bool flag;

// pair是将两种元素组成一对
pair<T1, T2> p;
p = make_pair(t1, t2); // 将t1、t2构造成一对
// pair支持比较,遵循字典序
p.first; // 访问第一个元素,这里是t1
p.second; // 访问第二个元素,这里是t2

// set内部是RB-tree维护
set<int> st; // 注意,set内元素不重复
st.insert(i); // 往set内插入一个元素i
// 时间复杂度O(log2(n)) 这里会返回一个<pair>迭代器
// first指向插入元素后所在的迭代器
// second指向是否插入成功(真值)
st.begin(); // 返回首迭代器
st.end(); // 范围尾迭代器
st.erase(it); st.erase(i);
// 删除某个元素
st.equal_range(i); // 返回几何中与i相等的上下限两个迭代器
flag = st.empty();
n = st.size();
st.clear();
// set内置了lower_bound和upeer_bound函数
// 用法和algorithm的一样

// 可重复元素set
multiset<int> mst;
// 用法与set大致相同
// 唯一不同只在删除函数上
mst.erase(i); // 会删除所有值为i的元素

return 0;
}
1
2
3
4
5
6
7
// 如果需要给set自定义排序顺序
struct CMP {
bool operator() (const int& a, const int& b) const {
return a > b; // 返回真值则代表左边的值优先级高
}
};
multiset<int, CMP> mst;
  • map(映射)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <map>
using namespace std;
int main() {
T1 t1;
T2 t2;

// map将两种元素做映射,一种指向另一种
// 内部也是RB-tree维护
map<T1, T2> mp;
mp[t1] = t2; // 直接让t1对应到t2
mp[t1]; // 访问t1对应的内容,时间复杂度O(log2(n))
// 如果t1没有指向任何内容,则会返回T2类型的初始值

return 0;
}
  • 一些C++的功能/特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h> // 标准库头文件
using namespace std;
int main() {

__int128 a; // 128位整数,最大值大概10^38次方
// C++11以上可用,无法用标准方法读入

cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
// 关闭cin、cout同步流,此举后不可混用scanf/printf

auto x; // 自动变量,可以是任意属性
// 举个例子
std::set<int> st;
std::for(auto i:st); // C++版for_each
// 其中i是auto变量,也可改成set<int>::iterator

// 所有的STL容器push/insert操作都可替换为emplcace
// 速度上减小常数(不用临时变量)
// 例:
int i;
std::set<int> st;
st.emplace(i);
std::vector<int> vc;
vc.emplace_back(i);

return 0;
}
  • 强大的pb_ds库

这部分并不是标准库STL,是扩展模板库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#include <bits/extc++.h> // 扩展库头文件
/*
* 这里如果没有bits/extc++.h的话需要
* ext/pb_ds/tree_policy.hpp
* ext/pb_ds/assoc_container.hpp
* ext/pb_ds/priority_queue_policy.hpp
* ext/pb_ds/trie_policy.hpp
* ext/rope
* ...
*/
using namespace __gnu_pbds;
using namespace __gnu_cxx;
int main() {

// 哈希表部分,用法与map一样,效率在C++11以下效率高
// 注意,这部分在namespace __gnu_pbds下
cc_hash_table<string, int> mp1; // 拉链法
gp_hash_table<string, int> mp2; // 查探法(快一些)

// 优先队列部分,比STL中高级
priority_queue<int, std::greater<int>, TAG> pq;
/*
* 第一个参数是数据类型
* 第二个是排序方式
* 第三个是堆的类型
* 其中堆的类型有下面几种
* pairing_heap_tag
* thin_heap_tag
* binomial_heap_tag
* c_binomial_heap_tag
* binary_heap_tag
* 其中pairing_heap_tag最快
* 并且这个东西是带默认参数的,只需要定义一个int
*/
// 比STL中的优先队列多了join和迭代器
// 例子:
priority_queue<int> pq1, pq2;
pq1.join(pq2); // 会将pq2合并到pq1上
pq1.begin(); pq1.end(); // 可遍历

// 红黑树(平衡树)部分,与set相似,但更快
tree <
int,
null_type,
std::less<>,
rb_tree_tag,
tree_order_statistics_node_update
> t, tre;
/*
* int 关键字类型
* null_type 无映射(低版本g++为null_mapped_type)
* less<int> 从小到大排序
* rb_tree_tag 红黑树(splay_tree_tag splay)
* tree_order_statistics_node_update 结点更新
*/
int i, k;
t.insert(i); // 插入
t.erase(i); // 删除
t.order_of_key(i);
// 询问这个tree中有多少个比i小的元素
t.find_by_order(k);
// 找第k + 1小的元素的迭代器,如果order太大会返回end()
t.join(tre); // tre合并到t上
t.split(i, tre); // 小于等于i的保留,其余的属于tre
// 基本操作有size()/empty()/begin()/end()等
// 同样内置lower_bound/upper_bound

// 可持久化平衡树部分
// 注意,这部分在namespace __gun_cxx下
rope<char> str;
// 待我学习完后再更新

return 0;
}

数据结构部分

  • 单调队列

1
// 待更新
  • 单调栈

可以O(n)O(n)地解决一些区间长度与区间最值关系问题。

例如:求nn个数中max[L,R]n{mini[L,R]{ai}(RL+1)}\displaystyle\max_{[L, R] \in n}\{\min_{i\in[L, R]}\{a_i\} \cdot (R-L+1)\}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define ll long long
const int MAX_N = 2e6 + 10;

struct data {
ll a, id;
}a[MAX_N];

stack<data> st;

int main() {
ll n, ans = 0;
data last;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i].a);
a[i].id = i;
if(st.empty()) st.push(a[i]);
else {
while(!st.empty() && st.top().a > a[i].a) {
last = st.top();
st.pop();
if(st.empty())
ans = max((i - 1) * last.a, ans);
else ans = max((i - st.top().id - 1) * last.a, ans);
} st.push(a[i]);
}
}
while(!st.empty()) {
last = st.top();
st.pop();
if(st.empty()) ans = max(n * last.a, ans);
else ans = max((n - st.top().id) * last.a, ans);
}
printf("%lld\n", ans);
return 0;
}
  • 归并排序、逆序对数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 归并排(升)序,p为逆序对数
#define mm (l + r) >> 1
#define lson l, mid
#define rson mid + 1, r
const int MAX_N = 1e5 + 10;
int a[MAX_N], tmp[MAX_N];
void m_sort(int l, int r, int &p) {
if(l == r) return ;
int mid = mm;
m_sort(lson, p), m_sort(rson, p);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r) {
if(a[i] <= a[j])
tmp[k++] = a[i++];
else {
tmp[k++] = a[j++];
p += mid - i + 1;
}
}
while(i <= mid) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for(i = l; i <= r; ++i) a[i] = tmp[i];
}
/*
* 逆序数的应用
* 1.假设序列中任意相邻数可以交换,逆序对数是让序列升序的最少交换次数
* 2.设f[n][m]代表逆序对数为m的n元排列个数,则有
* f[n + 1][m] = f[n][m] + f[n][m - 1] + …… + f[n][m - n]
* 化简得f[n + 1][m] = f[n][m] + f[n + 1][m - 1]
*/
  • 线段树/树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) (x & -x)
#define mm (l + r) >> 1
#define lson l, mid, p << 1 // 左儿子
#define rson mid + 1, r, p << 1|1 // 右儿子
const int MAX_N = 200000 + 10; // 数量大小

ll sum[MAX_N], tree[MAX_N << 2], lazy[MAX_N << 2], a[MAX_N];

inline void push_up(int p) {
tree[p] = tree[p << 1] + tree[p << 1|1];
}

inline void push_down(int l, int r, int p) {
if(lazy[p]) {
int mid = mm;
// 如果当前区间有lazy标记,则需要下放
tree[p << 1] += (mid - l + 1) * lazy[p];
tree[p << 1|1] += (r - mid) * lazy[p];
// 先更新两个儿子节点的值
lazy[p << 1] += lazy[p];
lazy[p << 1|1] += lazy[p];
// 标记下放到两个儿子节点
lazy[p] = 0; // 当前节点标记取消
}
}

void build(int l, int r, int p) {
if(l == r) {
tree[p] = a[l]; // 叶子节点信息
lazy[p] = 0;
return ;
}
int mid = mm;
build(lson), build(rson); // 分别往左往右
push_up(p); // 将儿子节点信息上传
}

ll query(int l, int r, int p, int L, int R) {
if(L <= l && r <= R) return tree[p];
// 区间包含则返回该节点所有信息
int mid = mm;
ll ret = 0; // ret用来保存信息
push_down(l, r, p); // 标记下放
if(L <= mid) ret += query(l, mid, p << 1, L, R);
// 取左区间的部分信息
if(R > mid) ret += query(mid + 1, r, p << 1|1, L, R);
// 取右区间的部分信息
return ret; // 将以上结果返回
}

void update(int l, int r, int p, int L, int R, int s) {
if(L <= l && r <= R) {
// 如果当前访问区间被要访问的区间所包含
tree[p] += (r - l + 1) * s;
// 首先更新当前节点的值
lazy[p] += s; // 打上lazy标签
return ;
}
int mid = mm;
push_down(l, r, p); // 标记下放
if(L <= mid) update(l, mid, p << 1, L, R, s);
// L <= mid 说明需要更新左区间
if(R > mid) update(mid + 1, r, p << 1 | 1, L, R, s);
// R > mid 说明需要更新右区间
tree[p] = tree[p << 1] + tree[p << 1|1];
// 别忘了要更新 p 节点的信息哦~
}

ll ask(int x) {
ll ret = 0;
for(; x; x -= lowbit(x)) ret += sum[x];
return ret;
}
ll get_sum(int l, int r) {
// 询问区间[l, r]的和
return ask(r) - ask(l - 1);
}
void change(int n, int x, ll s) {
// 给x位置上的值加上s
for(; x <= n; x += lowbit(x))
sum[x] += s;
}
  • 可持久化线段树(主席树)

    主席树本质上是n棵权值线段树,本质上不可修改,套上树状数组后可以支持单点修改(待更新)

  • 朴素版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 代码是求区间第k小的值
// 大部分情况需要离散化
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mm (l + r) >> 1
#define lson l, mid
#define rson mid + 1, r
const int MAX_N = (int)1e5 + 10;

struct node {
int ls, rs; // 用来存左右儿子下标
ll sum; // 数字和
}tree[MAX_N * 40];

int rt[MAX_N], CNT, a[MAX_N], p[MAX_N];
vector<int> vt;
// re是各版本线段树根节点下标 CNT是新建节点下标
// a是原数组,p是离散化后对应下标

int disc(int n) { // 离散化
for(int i = 1; i <= n; ++ i)
vt.push_back(a[i]);
sort(vt.begin(), vt.end());
unique(vt.begin(), vt.end());
for(int i = 1; i <= n; ++ i)
p[i] = lower_bound(vt.begin(), vt.end(), a[i]) - vt.begin() + 1;
}

int build(int l, int r) {
// 建立空树
int pos = ++ CNT;
if(l == r) return pos;
int mid = mm;
tree[pos].ls = build(lson); // 往左建树
tree[pos].rs = build(rson); // 往右建树
return pos;
}

inline void push_up(int pos) {
tree[pos].sum = tree[ tree[pos].ls ].sum + tree[ tree[pos].rs ].sum;
}

int update(int last, int l, int r, int k) {
// 更新第k点的值
int pos = ++ CNT;
if(l == r) {
tree[pos].sum = tree[last].sum + 1;
return pos;
}
int mid = mm;
tree[pos].ls = tree[last].ls, tree[pos].rs = tree[last].rs;
if(k <= mid)
tree[pos].ls = update(tree[last].ls, lson, k);
else
tree[pos].rs = update(tree[last].rs, rson, k);
push_up(pos);
return pos;
}


int query(int posL, int posR, int l, int r, int k) {
if(l == r) return l;
int cnt = (int)(tree[ tree[posR].ls ].sum - tree[ tree[posL].ls ].sum);
int mid = mm;
if(k <= cnt) return query(tree[posL].ls, tree[posR].ls, lson, k);
else return query(tree[posL].rs, tree[posR].rs, rson, k - cnt);
}

void init(int n) {
CNT = 0;
build(1, n);
for(int i = 1; i <= n*40; ++ i)
tree[i].sum = tree[i].ls = tree[i].rs = 0;
vt.clear();
}

int main() {
int n, q, i, l, r, k;

while(~ scanf("%d %d", &n, &q)) {
init(n); // 初始化
for(i = 1; i <= n; ++ i) scanf("%d", &a[i]);
disc(n);
for(i = 1; i <= n; ++ i)
rt[i] = update(rt[i - 1], 1, n, p[i]);
while(q --) {
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", vt[query(rt[l - 1], rt[r], 1, n, k) - 1]);
}
}

return 0;
}
  • 简约版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 简写主席树模板,没有建初始树过程
// 可以不要离散化,要注意空间
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 10;
#define ll long long
#define mm (l + r) >> 1
#define lson l, mid
#define rson mid + 1, r
struct node {
int ls, rs; // 用来存左右儿子下标
int sum; // 数字个数和
void copy(const node tmp) {
ls = tmp.ls;
rs = tmp.rs;
sum = tmp.sum;
}
}tree[MAX_N * 40];
int CNT, rt[MAX_N];
ll a[MAX_N];

void init(int n) {
CNT = 0;
for(int i = 1; i <= n*40; ++i)
tree[i].sum = tree[i].ls = tree[i].rs = 0;
for(int i = 0; i <= n; ++i) rt[i] = 0;
}

inline void push_up(int pos) {
tree[pos].sum = tree[ tree[pos].ls ].sum + tree[ tree[pos].rs ].sum;
}

void update(int &pos, int pre, ll l, ll r, ll val) {
pos = ++CNT;
tree[pos].copy(tree[pre]);
if(l == r) {
++tree[pos].sum;
return;
}
ll mid = mm;
if(val <= mid) update(tree[pos].ls, tree[pre].ls, lson, val);
else update(tree[pos].rs, tree[pre].rs, rson, val);
push_up(pos);
}

int query(int posL, int posR, ll l, ll r, int val) {
if(l == r) return l;
int cnt = (int)(tree[ tree[posR].ls ].sum - tree[ tree[posL].ls ].sum);
ll mid = mm;
if(val <= cnt) return query(tree[posL].ls, tree[posR].ls, lson, val);
else return query(tree[posL].rs, tree[posR].rs, rson, val - cnt);
}
  • 归并树(划分树)

    本质上是把归并排序和二叉树思想结合,可以解决部分主席树可以解决的东西,但不能回滚和修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 求区间第k小
#include <bits/stdc++.h>
using namespace std;
#define mm (l + r) >> 1
#define lson l, mid, dep + 1
#define rson mid + 1, r, dep + 1
const int MAX_N = 1e5 + 10;

int a[MAX_N], tree[32][MAX_N];

void build(int l, int r, int dep) {
if(l > r) return ;
if(l == r) {
tree[dep][l] = a[l];
return ;
}
int mid = mm, i = l, j = mid + 1, k = l;
build(lson), build(rson);
while(i <= mid && j <= r) {
if(tree[dep + 1][i] <= tree[dep + 1][j])
tree[dep][k ++] = tree[dep + 1][i ++];
else
tree[dep][k ++] = tree[dep + 1][j ++];
}
while(i <= mid)
tree[dep][k ++] = tree[dep + 1][i ++];
while(j <= r)
tree[dep][k ++] = tree[dep + 1][j ++];
return ;
}

int query(int l, int r, int dep, int ql, int qr, int key) {
if(qr < l || r < ql) return 0;
if(ql <= l && r <= qr)
return lower_bound(&tree[dep][l], &tree[dep][r] + 1, key) - &tree[dep][l];
int mid = mm, ret = 0;
if(qr > mid) ret += query(rson, ql, qr, key);
if(ql <= mid) ret += query(lson, ql, qr, key);
return ret;
}

int main() {
int n, m, i, ql, qr, k, l, r, mid, tot;
while(~scanf("%d %d", &n, &m)) {
for(i = 1; i <= n; ++i)
scanf("%d", &a[i]);
build(1, n, 1);
while(m --) {
scanf("%d %d %d", &ql, &qr, &k);
l = 1, r = n + 1, mid = mm;
while(l + 1 < r) {
mid = mm;
tot = query(1, n, 1, ql, qr, tree[1][mid]);
if(tot <= k - 1) l = mid;
else r = mid;
}
printf("%d\n", tree[1][l]);
}
}
return 0;
}
  • ST表(倍增)求区间最值

  • 一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 一维区间求最大值
const int MAX_N = 1e5 + 10;
int dp[MAX_N][20], vm[MAX_N];
/*
需要改成存最小(大)值下标,可以增加下列函数
int Min(int x, int y) {
return val[x] <= val[y] ? x : y;
}
*/
void init_RMQ(int n, int b[]) {
vm[0] = -1;
for(int i = 1; i <= n; ++i) {
vm[i] = ((i & (i-1)) == 0) ? vm[i - 1]+1 : vm[i - 1];
dp[i][0] = b[i];
}
for(int j = 1; j <= vm[n]; ++j)
for(int i = 1; i + (1<<j) - 1 <= n; ++i)
dp[i][j] = max(dp[i][j - 1], dp[i + (1<<(j-1)) ][j - 1]);
}
int RMQ(int l, int r) {
int k = vm[r - l + 1];
return max(dp[l][k], dp[r - (1<<k) + 1][k]);
}
  • 二维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 二维RMQ,预处理复杂度O(n * m * log2(n) * log2(m))
const int MAX_N = 310;
int val[MAX_N][MAX_N];
int dp[MAX_N][MAX_N][9][9];
int vm[MAX_N]; // 二进制位数-1,使用前需初始化

void init_VM() {
vm[0] = -1;
for(int i = 1; i < MAX_N; ++i)
vm[i] = ((i & (i-1)) == 0) ? vm[i - 1]+1 : vm[i - 1];
}

void init_RMQ(int n, int m) {
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
dp[i][j][0][0] = val[i][j];
for(int ii = 0; ii <= vm[n]; ++ii)
for(int jj = 0; jj <= vm[m]; ++jj)
if(ii + jj)
for(int i = 1; i + (1<<ii) - 1 <= n; ++i)
for(int j = 1; j + (1<<jj) - 1 <= m; ++j) {
if(ii) dp[i][j][ii][jj] = max(dp[i][j][ii - 1][jj],
dp[i + (1<<(ii-1)) ][j][ii - 1][jj]);
else dp[i][j][ii][jj] = max(dp[i][j][ii][jj - 1],
dp[i][j + (1<<(jj-1)) ][ii][jj - 1]);
}
}

int RMQ(int x1, int y1, int x2, int y2) {
// 求子矩阵最大值
int k1 = vm[x2 - x1 + 1];
int k2 = vm[y2 - y1 + 1];
x2 = x2 - (1<<k1) + 1;
y2 = y2 - (1<<k2) + 1;
return max( max(dp[x1][y1][k1][k2], dp[x1][y2][k1][k2]),
max(dp[x2][y1][k1][k2], dp[x2][y2][k1][k2]) );
}
  • 字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// k叉字典树,空间占用较大
struct Kx_Trie {
static const int MAX_N = 1010; // 节点数
static const int MAX_M = 26; // 字符数
static const int Tfirst = 'a'; // 第一个字符

int CNT;
struct node {
int son[MAX_M], sum; // sum是前缀数量
bool flag; // true代表这是个完整的单词
char c;
void init() {
sum = flag = c = 0;
memset(son, 0, sizeof(son));
}
}tree[MAX_N];

void init() {
CNT = 0;
tree[0].init();
}

void insert(char* str) {
int rt, nxt;
for(rt = 0; *str; rt = nxt, ++str) {
nxt = tree[rt].son[*str - Tfirst];
if(nxt == 0) {
nxt = tree[rt].son[*str - Tfirst] = ++CNT;
tree[CNT].init();
tree[CNT].c = *str;
}
++tree[nxt].sum;
} tree[rt].flag = true;
}

void erase(char* str) {
// 假设已经插入str
int rt = 0;
for(; *str; ++str) {
--tree[rt].sum;
rt = tree[rt].son[*str - Tfirst];
}
--tree[rt].sum;
tree[rt].flag = false;
}

bool search(char* str) {
// 查询是否有这个单词
int rt = 0;
for(; *str; ++str) {
rt = tree[rt].son[*str - Tfirst];
if(!rt) return false;
}
return tree[rt].flag;
}

int prefix(char *str) {
int rt, len;
for(rt = len = 0; *str; ++str, ++len) {
rt = tree[rt].son[*str - Tfirst];
if(!rt || !tree[rt].sum) break ;
}
return len;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 左孩子右兄弟字典树,时间换空间
struct Ls_Rb_Trie {
static const int MAX_N = 1010; // 节点数
int top;
struct node {
char c;
int l, r, sum;
bool flag;
void init() {
l = r = sum = flag = c = 0;
}
}tree[MAX_N];

void init() {
top = 0;
memset(tree, 0, sizeof(tree));
}

bool search(char* str) {
int rt;
for(rt = 0; *str; ++str) {
for(rt = tree[rt].l; rt; rt = tree[rt].r) {
if(tree[rt].c == *str) break ;
}
if(!rt || !tree[rt].sum) return false;
}
return tree[rt].flag;
}

void insert(char* str) {
int i, rt;
for(rt = 0; *str; ++str, rt = i) {
for(i = tree[rt].l; i; i = tree[i].r)
if(tree[i].c == *str)
break ;
if(i == 0) {
tree[rt].l = i = ++top;
tree[top].init();
tree[top].r = tree[rt].l;
tree[top].c = *str;
}
++tree[i].sum;
}
tree[rt].flag = true;
}

void erase(char* str) {
int rt;
for(rt = 0; *str; ++str) {
for(rt = tree[rt].l; rt; rt = tree[rt].r) {
if(tree[rt].c == *str)
break;
}
--tree[rt].sum;
}
tree[rt].flag = 0;
}

int prefix(char* str) {
// 最长前缀,
int rt = 0, lv;
for(lv = 0; *str; ++str, ++lv) {
for(rt = tree[rt].l; rt; rt = tree[rt].r)
if(tree[rt].c == *str)
break ;
if(rt == 0 || !tree[rt].sum) break ;
}
return lv;
}
};
  • 树链剖分

  • 点权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// 查询单点值,修改路径上的点权,HDU3966
const int MAX_N = 5e4 + 10;
struct node {
int to, go;
}edge[MAX_N << 1];
int head[MAX_N], tot, pos;
int top[MAX_N]; // top[v]表示v所在重链的顶端节点
int fa[MAX_N]; // 父亲节点
int deep[MAX_N]; // 深度
int num[MAX_N]; // num[v]表示v为根的子树节点数量
int p[MAX_N]; // p[v]表示v对应的位置
int fp[MAX_N]; // fp和p数组相反
int son[MAX_N]; // 重儿子

void init() {
tot = 0;
memset(head, -1, sizeof(head));
pos = 1; // 树状数组编号
memset(son, -1, sizeof(son));
}

void add_edge(int u, int v) {
edge[tot].to = v, edge[tot].go = head[u], head[u] = tot++;
}

void dfs(int u, int pre, int dep) {
deep[u] = dep;
fa[u] = pre;
num[u] = 1;
for(int i = head[u]; i != -1; i = edge[i].go) {
int v = edge[i].to;
if(v != pre) {
dfs(v, u, dep+1);
num[u] += num[v];
if(son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
}

void get_pos(int u, int sp) {
top[u] = sp;
p[u] = pos++;
fp[p[u]] = u;
if(son[u] == -1) return ;
get_pos(son[u], sp);
for(int i = head[u]; i != -1; i = edge[i].go) {
int v = edge[i].to;
if(v != son[u] && v != fa[u])
get_pos(v, v);
}
}

// 树状数组部分
int c[MAX_N];
int n;

inline int lowbit(int x) {
return x & (-x);
}

int get_sum(int i) {
int s = 0;
while(i > 0) {
s += c[i];
i -= lowbit(i);
}
return s;
}

void add(int i, int val) {
while(i <= n) {
c[i] += val;
i += lowbit(i);
}
}

// u->v路径上的点值改变为val
void update(int u, int v, int val) {
int f1 = top[u], f2 = top[v];
while(f1 != f2) {
if(deep[f1] < deep[f2]) {
swap(f1, f2);
swap(u, v);
}
add(p[f1], val);
add(p[u]+1, -val);
u = fa[f1];
f1 = top[u];
}
if(deep[u] > deep[v]) swap(u, v);
add(p[u], val);
add(p[v]+1, -val);
}

int a[MAX_N];

int main() {
int m, q;
while(~ scanf("%d %d %d", &n, &m, &q)) {
int u, v, k;
char op[10];
init();
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
while(m--) {
scanf("%d %d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
dfs(1, 0, 0);
get_pos(1, 1);
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; ++i) {
add(p[i], a[i]);
add(p[i]+1, -a[i]);
}
while(q--) {
scanf("%s", op);
if(op[0] == 'Q') {
scanf("%d", &u);
printf("%d\n", get_sum(p[u]));
} else {
scanf("%d %d %d", &u, &v, &k);
if(op[0] == 'D') k = -k;
update(u, v, k);
}
}
}
return 0;
}
  • 边权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// 修改单条边,查询路径边权最大值 SPOJ QTREE
#define mm (l + r) >> 1
#define lson l, mid, p << 1
#define rson mid + 1, r, p << 1|1
const int MAX_N = 1e5 + 10;
struct node {
int to, go;
}edge[MAX_N << 1];
int head[MAX_N], tot, pos;
// tot是边表下标,pos是剖分后点个数(1开始)
int top[MAX_N]; // top[v]表示v所在重链的顶端节点
int fa[MAX_N]; // 父亲节点
int deep[MAX_N]; // 深度
int num[MAX_N]; // num[v]表示v为根的子树节点数量
int p[MAX_N]; // p[v]表示v对应的位置
int fp[MAX_N]; // fp和p数组相反
int son[MAX_N]; // 重儿子

void init() {
tot = 0;
memset(head, -1, sizeof(head));
pos = 1;
memset(son, -1, sizeof(son));
}

void add_edge(int u, int v) {
edge[tot].to = v, edge[tot].go = head[u], head[u] = tot++;
}

//第一遍 dfs 求出fa, deep, num, son
void dfs(int u, int pre, int dep) {
deep[u] = dep;
fa[u] = pre;
num[u] = 1;
for(int i = head[u]; i != -1; i = edge[i].go) {
int v = edge[i].to;
if(v != pre) {
dfs(v, u, dep+1);
num[u] += num[v];
if(son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
}

//第二遍 dfs 求出top, p
void get_pos(int u, int sp) {
top[u] = sp;
p[u] = pos++;
fp[p[u]] = u;
if(son[u] == -1) return ;
get_pos(son[u], sp);
for(int i = head[u]; i != -1; i = edge[i].go) {
int v = edge[i].to;
if(v != son[u] && v != fa[u])
get_pos(v, v);
}
}

// 线段树部分
int tree[MAX_N << 2];

inline void push_up(int p) {
tree[p] = max(tree[p << 1], tree[p << 1|1]);
}

void build(int l, int r, int p) {
if(l == r) {
tree[p] = 0;
return ;
}
int mid = mm;
build(lson), build(rson);
}

void update(int l, int r, int p, int k, int val) {
if(l == r && r == k) {
tree[p] = val;
return ;
}
int mid = mm;
if(k <= mid) update(lson, k, val);
else update(rson, k, val);
push_up(p);
}

int query(int l, int r, int p, int L, int R) {
if(L <= l && r <= R) return tree[p];
int mid = mm, ret = INT_MIN;
if(L <= mid) ret = max(ret, query(lson, L, R));
if(R > mid) ret = max(ret, query(rson, L, R));
return ret;
}

int find(int u, int v) {
// 查询u->v上最大边权
int f1 = top[u], f2 = top[v];
int tmp = 0;
while(f1 != f2) {
if(deep[f1] < deep[f2]) {
swap(f1, f2);
swap(u, v);
}
tmp = max(tmp, query(1, pos, 1, p[f1], p[u]));
u = fa[f1], f1 = top[u];
}
if(u == v) return tmp;
if(deep[u] > deep[v]) swap(u, v);
return max(tmp, query(1, pos, 1, p[ son[u] ], p[v]));
}

int G[MAX_N][3];

int main() {
int T, n, u, v;
char op[10];
scanf("%d", &T);
while(T --) {
init();
scanf("%d", &n);
for(int i = 1; i < n; ++i) {
scanf("%d %d %d", &G[i][0], &G[i][1], &G[i][2]);
add_edge(G[i][0], G[i][1]);
add_edge(G[i][1], G[i][0]);
}
dfs(1, 0, 0);
get_pos(1, 1);
build(1, pos, 1);
for(int i = 1; i < n; ++i) {
if(deep[ G[i][0] ] > deep[ G[i][1] ])
swap(G[i][0], G[i][1]);
update(1, pos, 1, p[ G[i][1] ], G[i][2]);
}
while(scanf("%s", op)) {
if(op[0] == 'D') break ;
scanf("%d %d", &u, &v);
if(op[0] == 'Q')
printf("%d\n", find(u, v));
else update(1, pos, 1, p[ G[u][1] ], v);
}
}
return 0;
}
  • 并查集

  • 普通并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int MAX_N = 1e5 + 10;
int f[MAX_N];
void init(int n) {
for(int i = 0; i <= n; ++i)
f[i] = i;
}
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return false ;
f[y] = x;
return true; // false表示已经在同一集合
}
  • 带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int MAX_N = 1e5 + 10;
const int MOD = 3;
// MOD实际上指的是关系数
int f[MAX_N], p[MAX_N];
// p数组存权值

void init(int n) {
for(int i = 0; i <= n; ++i)
f[i] = i, p[i] = 0;
}

int find(int x) {
int tmp = f[x];
if(f[x] != x) {
f[x] = find(f[x]); // 压缩路径
p[x] = (p[x] + p[tmp]) % MOD;
// 合并权值
}
return f[x];
}

void merge(int x, int y, int s) {
// 合并集合并加权,这里一般要s-1
int fx = find(x), fy = find(y);
if(fx != fy) {
f[fy] = fx;
p[fy] = (p[x] - p[y] + s + MOD) % MOD;
}
}

bool solve(int x, int y, int ask, int n) {
// 判断x、y权值关系,是否满足要求
int fx = find(x), fy = find(y);
bool flag = true;
if(x > n || y > n || (ask == 1 && x == y))
flag = false ;
else if(fx == fy)
flag = ((p[y] - p[x] + MOD) % MOD == ask);
return flag;
}

数论部分

  • 一些基础的公式、定理

  1. 组合数公式:Cnm=Cn1m1+Cn1mC_n^m = C_{n-1}^{m-1} + C_{n-1}^m,即杨辉三角,可用在O(n2)O(n^2)下求出所有组合数
  2. Lucas定理:Cnm=Cn/pm/pCn%pm%pmodpC_n^m = C_{n/p}^{m/p} * C_{n\%p}^{m\%p} \mod p,要求pp是质数
  3. 错排公式:an=(n1)an1an2a_n = (n-1) * a_{n-1} * a_{n-2}
  4. 欧拉定理:若gcd(a,n)=1gcd(a,n) = 1,则有aϕ(n)1(modn)a^{\phi(n)} \equiv 1 \pmod n,其中ϕ(n)\phi(n)是欧拉函数。
  5. 费马小定理:若gcd(a,p)=1gcd(a, p) = 1,则有ap11(modp)a^{p-1} \equiv 1 \pmod p
  6. 费马大定理:当n>2n > 2时,xn+yn=znx^n + y^n = z^n没有正整数解
  7. 威尔逊定理:当且仅当pp是素数时,有(p1)!1(modp)(p-1)! \equiv 1 \pmod p
  8. 快速幂:对于任意正整数a,na,n,满足an={(an/2)2n是偶数a(an/2)2n是奇数a^n = \begin{cases} {(a^{n/2})}^2 &\text{n是偶数} \\ a * (a^{n/2})^2 &\text{n是奇数} \end{cases}
  9. 平方和公式:x=1nx2=(2n+1)(n+1)n/6\sum_{x=1}^n x^2 = (2*n + 1) * (n + 1) * n / 6
  10. 等比数列求和:Sn=a1(1qn)/(1q)S_n = a_1 * (1-q^n) / (1-q)
  11. 素数间隔定理:对于大质数pnp_npn1p_{n-1}之间间隔不超过log2pn\log_2p_n
  12. 待更新……
  • 因数、余数、质数基础

  • 埃氏素数筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
const int MAX_N = 1e5 + 10;
int CNT, prime[MAX_N];
bool vis[MAX_N];
void make_prime() {
CNT = 0;
for(int i = 2; i < MAX_N; ++i) {
if(!vis[i]) {
prime[++CNT] = i;
for(int j = 2; j * i < MAX_N; ++j)
vis[i*j] = true;
}
}
}
  • 欧拉函数

对于任意正整数nn,欧拉函数是[1,n][1,n]中与nn互质的数的个数,通常写作φ(n)\varphi(n)。特别地,φ(1)=1\varphi(1) = 1

通式为:φ(x)=xi=1n(11pi)\varphi(x) = x \displaystyle\prod_{i=1}^{n} (1 - \frac{1}{p_i}),其中p1,p2,,pnp_1, p_2, \dots, p_nnn的所有质因子。

  1. 求解单个数字其欧拉函数:
1
2
3
4
5
6
7
8
9
10
11
int phi(int n) {
int ans = n;
for(int i = 2; i * i <= n; ++i) {
if(n % i == 0) {
ans -= ans / i;
while(n % i == 0) n /= i;
}
}
if(n > 1) ans -= ans / n;
return ans;
}
  1. 打表求欧拉函数:
1
2
3
4
5
6
7
8
9
10
11
12
const int MAX_N = 1e5 + 10;
int phi[MAX_N];
void euler() {
for(int i = 2; i < MAX_N; ++i) {
if(!phi[i]) {
for(int j = i; j < MAX_N; j += i) {
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i-1);
}
}
}
}
  1. 线性筛素数、欧拉函数:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MAX_N = 1e6 + 10;
int CNT, prime[MAX_N], phi[MAX_N];
bool vis[MAX_N];
void make_prime_phi() {
CNT = 0;
memset(vis, false, sizeof(vis));
for(int i = 2; i < MAX_N; ++i) {
if(!vis[i]) {
prime[++CNT] = i;
phi[i] = i-1;
}
for(int j = 1; j <= CNT && i*prime[j] < MAX_N; ++j) {
vis[ i*prime[j] ] = true;
if(i % prime[j] == 0) {
phi[ i*prime[j] ] = phi[i] * prime[j];
break ;
} else phi[ i*prime[j] ] = phi[i] * (prime[j]-1);
}
}
}

欧拉函数的一些性质:

  1. gcd(n,m)=1gcd(n, m) = 1,则φ(nm)=φ(n)φ(m)\varphi(nm) = \varphi(n) \varphi(m)
  2. n>2n>2时,所有的φ(n)\varphi(n)都是偶数
  3. nn为奇数时,有φ(2n)=φ(n)\varphi(2n) = \varphi(n)
  4. gcd(i,n)=1ni=nφ(n)/2\displaystyle\sum_{gcd(i, n) = 1}^{n}{i} = n * \varphi(n) / 2
  5. dnφ(d)=n\displaystyle\sum_{d|n} \varphi(d) = n
  • 欧几里得定理求a、b最大公因数、最小公倍数

1
2
3
4
5
6
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
  • 扩展欧几里得

求一组整数特解(x,y)(x, y),满足ax+by=gcd(a,b)ax + by = gcd(a, b),其中aabb已知。

易知上述方程可转化为bx+(a%b)y=gcd(b,a%b)=gcd(a,b)bx' + (a \% b)y' = gcd(b, a \% b) = gcd(a, b)

则有ax+by=bx+(a%b)yax + by = bx' + (a \% b)y',整理后得

ax+by=ay+b(xaby)ax + by = ay' + b(x' - \lfloor{\frac{a}{b}}\rfloor y')

得出解:x=y,y=xabyx = y', y = x' - \lfloor{\frac{a}{b}}\rfloor y'