为了熟悉各类算法原理，在这里整理一下一些需要经常练习的算法。

扩展欧几里得ex_gcd（求解ax + by = gcd(a, b) (mod p)）

P1082 [NOIP2012 提高组] 同余方程 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Problem - 2669 (hdu.edu.cn)

用于计算\(ax + by = c(mod p)\)的最小正整数解，如果\(c\)不是\(gcd(a, b)\)的倍数则无解。

void ex_gcd(int a,int b,int &d,int &x,int &y)
{
	if(!b)d = a, x = 1, y = 0;
	else ex_gcd(b, a % b, d, y, x), y -= x * (a / b);
}

记住ax = 1就可以记住d = a, x = 1, y = 0，记住b和a辗转相除，x, y换位置。

经常用于\(p = b\)的情况下求解，记得将x扩大c/d倍(x = x * c / d)，因为用ex_gcd算出的x是在右侧等于gcd(a, b)的结果。

在算出x之后要使得x在modp意义下，所以需要对x取模加p再取模。

int d = 0, x = 0, y = 0;
ex_gcd(a, b, d, x, y);
if(p % d == 0)p /= d;
x = x * c / d;
x = (x % p + p) % p;

五行经典代码绝不出错。

主席树（类似树状数组，带前缀和的树）

P1972 [SDOI2009] HH的项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P3834 【模板】可持久化线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

注意区间是[0, N]还是[1, N]，root[i]表示第i个版本的根，插入函数要牢记，插入、查询函数记得判断x大小切掉一半的递归，确保每次只往一个方向递归。

主席树可以维护一个区间内的第k大的值，也可以维护区间数字的种类数。

树状数组（区间修改，区间查询）

P3368 【模板】树状数组 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间修改的树状数组用到了差分的思想，设差分数组为d，我们知道\(a[i] = \sum_{1}^{i}d[i]\)，利用这个特性，可以知道\(\sum_{i = 1}^{N}a[i] = \sum_{i = 1}^{N}\sum_{j = 1}^{i}d[i]\)，这个式子展开后容易发现\(\sum_{1}^{k}a[i] = \sum_{i = 1}^{k}k * d[i] - (i - 1)d[i]\)，所以我们只需要维护一个\(d[i]\)和\((i - 1)d[i]\)即可，或者是\(d[i]\)和\(id[i]\)也可以。这里的k是随着查询而变化的，而i在修改的时候是不变的。

void add(int k,int x){for(int i = k;i <= N; i += lowbit(i))d[i] += x, di[i] += k * x;}
int getsum(int k)
{
	int res = 0;
	for(int i = k;i > 0; i -= lowbit(i))res += (k + 1) * d[i] - di[i];
	return res;
}

狠狠记住。