FUN WORLD

约数个数 @Ubospica 对于约数个数上界的估计 d(n)≤ncln⁡ln⁡nd(n)\le n^{\frac c{\ln\ln n}}d(n)≤nlnlnnc​，其中 c≈1.066c\approx1.066c≈1.066。当 n>5000n>5000n>5000 约有 d(n)<nd(n)<\sqrt nd(n)<n​。 质数判定 关于质数判定的一些资料： @wangrx 一定范围内的确定性判素 知乎 如何编程判断一个数是否是质数？ 费马素性检验 / 费马测试 费马小定理的逆否命题：若存在 1≤a<p1\le a<p1≤a<p，使得 ap−1≢1(modp)a^{p-1}\not\equiv1\pmod pap−1≡1(modp)，则 ppp 一定不是素数。 多次选取质数 a∈[1,p)a\in[1,p)a∈[1,p)，使用快速幂检查 pa−1 mod pp^{a-1}\bmod ppa−1modp 是否为 111：若存在快速幂的结果不是 111，则 ppp 一定不是素数；否则 ppp 大概率是素数。 遗憾的 ...

决策单调性优化 DP 2D/1D DP 的决策单调性优化 2D/1D DP 指状态有两维、转移有一维的 DP。 定理：对于形如 f(i,j)=min⁡k=ij−1{f(i,k)+f(k+1,j)}+w(i,j)f(i,j)=\min\limits_{k=i}^{j-1}\{f(i,k)+f(k+1,j)\}+w(i,j)f(i,j)=k=iminj−1​{f(i,k)+f(k+1,j)}+w(i,j) 的 DP 式，若： 区间包含单调性：对于 i≤i′<j≤j′i\le i'<j\le j'i≤i′<j≤j′，满足 w(i′,j)≤w(i,j′)w(i',j)\le w(i,j')w(i′,j)≤w(i,j′)。（（互相包含的两个区间）大区间大于小区间） 四边形不等式：对于 i≤i′<j≤j′i\le i'<j\le j'i≤i′<j≤j′，满足 w(i,j)+w(i′,j′)≤w(i′,j)+w(i,j′)w(i,j)+w(i',j')\le w(i&#x ...

有源汇最大流算法家族 EK BFS 寻找最短增广路。 时间复杂度 O(n2m2)O(n^2m^2)O(n2m2)。 Dinic Dinic 是 EK 的优化。 BFS 得到距离标号，用 DFS 同时增广相同长度的增广路。 反向标号：从 TTT 开始 BFS 重算距离标号，从 SSS​ 开始 DFS。 时间复杂度 O(n2m)O(n^2m)O(n2m)。 在边权全为 111 的图上跑最大流的时间复杂度为 O(min⁡{n23m,m32})O(\min\{n^{\frac23}m,m^{\frac32}\})O(min{n32​m,m23​})。 ISAP ISAP 可视为 Dinic 的优化。 在 DFS 之后直接 distu=min⁡{distv}+1\text{dist}_u=\min\{\text{dist}_v\}+1distu​=min{distv​}+1。 再加一个 gapx\text{gap}_xgapx​​ 表示 ∑[distu=x]\sum[\text{dist}_u=x]∑[distu​=x]​。若 gapx\text{gap}_xgapx​ 断层，则不可能再 ...

注意事项 负数 >> 1 和 / 2 不同，右移是向下取整，除法是向零取整。e.g. (-5) >> 1 = -3, (-5) / 2 = -2。 pb_ds 库 所有数据结构都在 __gnu_pbds 命名空间。 哈希表 头文件： 12#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> 定义： 拉链法处理冲突 cc_hash_table<key_type, value_type> hash_name 探测法处理冲突 gp_hash_table<key_type, value_type> hash_name（较快） 成员函数： hash_name[key] 重载中括号运算符访问 value 值的引用，若 value 值不存在则新开辟空间。 iterator find(key_type num) 返回按 key 查找到的 value 值的迭代器，未找到返回 hash_name.end()。 平 ...