一些有用的tricks 发表于 2022-12-12 分类于 学习笔记 图论 边的形式统一的完全图用虚点。 边权按端点信息生成的图求最小生成树，考虑 Boruvka 算法。 数学 异或比大小考虑 trie 树。 质因数分解朴素 O(n)O(\sqrt{n})O(n)；预处理 n\sqrt{n}n 以内的质数（假设有 cntcntcnt 个）后可以做到 O(cnt)≈n10O(cnt)\approx\frac{\sqrt{n}}{10}O(cnt)≈10n；预处理 nnn 以内每个数的最小质因子后可以做到 O(log(n))O(\log(n))O(log(n))。 数组中 gcd\gcdgcd 为 iii 的数对的个数，可以设 f[i]f[i]f[i] 表示 iii 的倍数的个数，则 数据结构 DP