为了熟悉各类算法原理，在这里整理一下一些需要经常练习的算法。
扩展欧几里得ex_gcd（求解ax + by = gcd(a, b) (mod p)）
P1082 [NOIP2012 提高组] 同余方程 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.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;
}
狠狠记住。
文章评论