原根
\(m\) 有原根，当且仅当 \(m\) 形如：\(2\)、\(4\)、\(p^k\)、\(2p^k\)（\(k\in \mathbf{N}^*\)）。
若 \(m\) 有原根，则有 \(\varphi(\varphi(m))\) 个原根。
最小原根量级为 \(\mathcal{O}(n^{1/4})\)。
\(m\ge 3\)，\(\gcd(m,t)=1\) 时，\(t\) 是原根的充要条件为：
- \(\forall p\mid\varphi(m),t^{\varphi(m)/p}\not\equiv m\pmod m\)。
凸包
选出 \(x\) 最小的点中 \(y\) 最小的点 \(s\)，以 \(s\) 为原点对其他点按极角排序。
- 计算极角使用
atan2(y, x)，极角相同时按照 \(x\) 比较，若 \(x\) 相同则按照 \(y\) 比较（重要）。
按顺序加点。维护一个栈，站内初始为最前两个点。新加点时，若栈顶两点与新加入点的叉积非负，栈顶一定不在凸包内，弹栈。
注意特判 \(n=1\)。
时间复杂度 \(\mathcal{O}(n\log n)\)。
评测记录。
斜率优化
转移形如：
\[f_i=\min\limits_{j<i}\{F(j)+w(i)w'(j)\} \]直线方程 \(y=kx+b\)，移项得 \(b=y-kx\)。
考虑 \((x_j,y_j)\)，其中：
\[\begin{aligned} x_j &= -w'(j) \\ y_j &= F(j) \end{aligned} \]\(f_i\) 即所有斜率为 \(k=w(i)\) 且经过任意 \((x_j,y_j)\) 的直线中截距最小的。
对所有 \(k\)，最优转移一定在（下）凸壳上。
若 \(x_j\) 及 \(k\) 均单调，可以使用单调队列求出最优转移，时间复杂度 \(\mathcal{O}(n)\)。
下面三种都没写过：
\(x_j\) 单调时，二分凸壳上的切点，时间复杂度 \(\mathcal{O}(n\log n)\)。
\(k\) 单调时，动态维护凸包，时间复杂度 \(\mathcal{O}(n\log n)\)。
否则，使用 CDQ 分治，时间复杂度 \(\mathcal{O}(n\log^2 n)\)。
错误的，使用李超树，时间复杂度 \(\mathcal{O}(n\log n)\)。
无向图三元环计数
度数大的向小的连边，度数相同按照编号连边。
时间复杂度 \(\mathcal{O}(m\sqrt m)\)。证明：
考虑 \(u\to v\)，代价为 \({\rm out}_v\)。
- \({\rm out}_v\le \sqrt m\)：共 \(m\) 条边，复杂度不超过 \(\mathcal{O}(m\sqrt m)\)；
- \({\rm out}_v>\sqrt m\)：不超过 \(m/\sqrt m=\sqrt m\) 个 \(u\) 向 \(v\) 有连边，所有满足条件的 \(v\) 的 \(\sum {\rm out}_v\le m\)，复杂度不超过 \(\mathcal{O}(m\sqrt m)\)。
exGCD
求一组 \((x,y)\) 满足 \(ax+by=\gcd(a,b)\)。
先求出 \(a'=b,b'=a\bmod b\) 的一组解 \((y',x')\)，有：
\[\begin{aligned} \gcd(a,b) &= a'y'+b'x' \\ &= (a\bmod b)x'+by' \\ &= (a-\lfloor\dfrac ab\rfloor b)x'+by' \\ &= ax'+b(y'-\lfloor\dfrac ab\rfloor x') \end{aligned} \]令 \(x\gets x'\)、\(y\gets y'-\lfloor\dfrac ab\rfloor x'\) 即可。
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) return x = 1, y = 0, a;
ll g = exgcd(b, a % b, y, x);
return y -= a / b * x, g;
}
exCRT
合并：
\[\begin{cases} X &\equiv a &\pmod p \\ X &\equiv b &\pmod q \end{cases} \]\[\begin{aligned} a+xp &\equiv b &\pmod q \\ xp &\equiv b-a &\pmod q \end{aligned} \]用 exgcd 求出 \(x'p+y'q=\gcd(p,q)\)，有解当且仅当 \(\gcd(p,q)\mid (b-a)\)。
记 \(d=(b-a)/g\)，则 \(x=x'd\)，答案即为 \(a'=a+xp=a+x'dp\)。
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) return x = 1, y = 0, a;
ll g = exgcd(b, a % b, y, x);
return y -= a / b * x, g;
}
ll norm(ll x, ll p) { return x %= p, x < 0 ? x + p : x; }
void CRT(ll &a, ll &p, ll b, ll q) {
ll x, y, g = exgcd(p, q, x, y), d = norm(b - a, q) / g;
ll t = p; p = p / g * q;
a = norm(a + (__int128)x * t % p * d % p, p);
}