常用模板整理

考前不必把代码全重写，把最常用的模板整理成一个文件，翻一遍就能唤醒记忆。快速幂算 $a^b\mathrm{mod}p$ 是必备的一个：

long long qpow(long long a, long long b, long long p) {
    long long res = 1 % p;
    while (b) {
        if (b & 1) res = res * a % p;  // 当前二进制位是 1 就乘上
        a = a * a % p;                 // 底数平方
        b >>= 1;
    }
    return res;
}

它把 $O(b)$ 的乘法降到 $O(\log b)$。同一个文件里还该放：辗转相除求 gcd、埃氏筛质数 $O(n\log \log n)$、二分 $O(\log n)$、归并排序 $O(n\log n)$。整理的过程本身就是一次复习。