模板要背熟

二分、快速幂、辗转相除、筛质数、并查集——这几个是最常用的"零件"，考场上必须能秒写，不能现推。现推既慢又容易错，把宝贵时间浪费在造轮子上。

其中快速幂最容易记错，重点默熟它：

long long qpow(long long a, long long b, long long mod) {
    long long res = 1 % mod;
    while (b) {
        if (b & 1) res = res * a % mod;  // 当前二进制位为 1 就乘
        a = a * a % mod;                 // 底数自乘
        b >>= 1;                         // 指数右移一位
    }
    return res;
}

原理是把指数按二进制拆开，每一位对应一个 $a^{2^k}$，所以只需 $O(\log b)$ 次乘法就能算出 $a^b\mathrm{mod}m$。

两个高频坑：中间乘积 res * a 可能超过 int，全程用 long long 并及时取模；辗转相除 gcd(a,b) 的递归边界是 b==0 时返回 a，别写反。把这五个模板抄在一张纸上反复默写，直到闭眼能敲。