一、数论
1. 质数
   1.1. 米勒-拉宾素性检验 O(7 * logx * O(qmul))
       ll qmul(ll a, ll b, ll p)
    {
        ll c = (long double)a / p * b;
        ll res = (ull)a * b - (ull)c * p;
        return (res + p) % p;
    }

    ll qpow(ll a, ll b, ll p)
    {
        ll ans = 1;
        for (; b; b >>= 1)
        {
            if (b & 1) ans = qmul(ans, a, p);
            a = qmul(a, a, p);
        }
        return ans;
    }

    bool isprime(ll x)
    {
        if (x < 3) return x == 2;
        if (!(x & 1)) return false;
        ll A[] = {0, 2, 325, 9375, 28178, 450775, 9780504, 1795265022};
        ll d = x - 1, r = 0;
        while (d % 2 == 0)
        {
            r++;
            d /= 2;
        }
        for (auto a : A)
        {
            ll v = qpow(a, d, x);
            if (v <= 1 || v == x - 1) continue;
            for (int i = 1; i <= r; i++)
            {
                v = qmul(v, v, x);
                if (v == x - 1  && i != r)
                {
                    v = 1;
                    break;
                }
                if (v == 1)
                    return false;
            }
            if (v != 1)
                return false;
        }
        return true;
    }

    1.2. 线性筛求质数
    void primes(int n)
    {
        for (int i = 2; i <= n; i++)
        {
            if (v[i] == 0)
                v[i] = i, prime[++m] = i;
            for (int j = 1; j <= m; j++)
            {
                if (prime[j] > v[i] || prime[j] * i > n) break;
                v[prime[j] * i] = prime[j];
            }
        }
    }

2. 约数
    2.1. 求某个数的约数集合
    // 参数 n >= 1 , fact存的约数不是有序的; O(sqrt(n))
    void facts(ll n)
    {
        m = 0;
        for (int i = 1; (ll)i * i <= n; i++)
            if (n % i == 0)
            {
                fact[++m] = i;
                if (i != n / i) fact[++m] = n / i;
            }
    }
    2.2. 欧拉函数
        2.2.1 求某个数的欧拉函数
        // 参数 n >= 1; O(sqrt(n))
        int geteuler(int n)
        {
            int ans = n;
            for (int i = 2; i * i <= n; i++)
                if (n % i == 0)
                {
                    ans = ans / i * (i - 1);
                    while (n % i == 0) n /= i;
                }
            if (n > 1) ans = ans / n * (n - 1);
            return ans;
        }

        2.2.2 线性筛欧拉函数
        //
        void euler(int n) {
            memset(v, 0, sizeof(v)); // 最小质因子
            m = 0; // 质数数量
            phi[1] = 1;
            for (int i = 2; i <= n; i++) {
                if (v[i] == 0) { // i是质数
                    v[i] = i, prime[++m] = i;
                    phi[i] = i - 1;
                }
                // 给当前的数i乘上一个质因子
                for (int j = 1; j <= m; j++) {
                    // i有比prime[j]更小的质因子，或者超出n的范围
                    if (prime[j] > v[i] || prime[j] > n / i) break;
                    // prime[j]是合数i*prime[j]的最小质因子
                    v[i*prime[j]] = prime[j];
                    phi[i*prime[j]] = phi[i] * (i%prime[j] ? prime[j]-1 : prime[j]);
                }
            }
        }


3. 同余
    3.1. exgcd
    // log (a + b); a, b是整数
    ll exgcd(ll a, ll b, ll &x, ll &y)
    {
        if (!b)
        {
            x = 1, y = 0;
            return a;
        }
        ll d = exgcd(b, a % b, x, y);
        ll z = x;
        x = y;
        y = z - y * (a / b);
        return d;
    }

    3.2. 中国剩余 (解方程组 x = ai (mod mi) -> 表示第i个方程. 求解x)
    //要求任意 mi 与 mj (i != j) 互质，方程通解为 x + k * M ( k 是任意整数)
    int n;
    int m[N], a[N];
    int main()
    {
        scanf("%d", &n);
        ll M = 1;
        for (int i = 1; i <= n; i++) 
        {
            cin >> m[i] >> a[i];
            M *= m[i];
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++)
        {
            ll Mi = M / m[i];
            ll ti, y;
            exgcd(Mi, m[i], ti, y);
            ans += a[i] * Mi * ti;
        }
        cout << (ans % M + M) % M << endl;
    }

    3.3 逆元
        3.3.1. exgcd求x的逆元(x与mod互质,即存在逆元,可通过此方法求)

        3.3.2. qmi求逆元(要求逆元存在并且mod是质数) 

        3.3.3. 线性预处理1~n逆元(要求逆元存在并且mod是质数)
        // O(n)
        inv[1] = 1;
        for (int i = 2; i <= 1005; i++)
            inv[i] = (mod - mod / i) * inv[mod % i] % mod;

        3.3.4 线性预处理阶乘(jie[1] ~ jie[n])的逆元 (要求逆元存在并且mod是质数)
        // O(n)
        inv[0] = 1, inv[1] = 1;
        for (int i = 2; i <= 1005; i++)
            inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        for (int i = 2; i <= 1005; i++)
            inv[i] = inv[i - 1] * inv[i] % mod;

4. 矩阵
    4.1. 矩阵乘法
    //1行3列 * 3行3列 = 1行3列, 最终答案覆盖f[]
    void mul(int f[3], int a[3][3])
    {
        int c[3];
        memset(c, 0, sizeof(c));
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                c[j] = (c[j] + (ll)f[k] * a[k][j] % mod) % mod;
        memcpy(f, c, sizeof(c));
    }
    //3行3列 * 3行3列 = 3行3列, 最终答案覆盖a[][]
    void mulself(int a[3][3], int b[3][3])
    {
        int c[3][3];
        memset(c, 0, sizeof(c));
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    c[i][j] = (c[i][j] + (ll)a[i][k] * b[k][j] % mod) % mod;
        memcpy(a, c, sizeof(c));
    }

    4.2. 高斯消元
    //O(n^3)
    // a[N][N]是增广矩阵, 唯一解返回0, 无穷解1, 无解-1
    int gauss()
    {
        int r, c;
        for (r = 0, c = 0; c < n; c++)
        {
            int t = r;
            for (int i = r; i < n; i++)
                if (fabs(a[i][c]) > fabs(a[t][c]))
                    t = i;

            if (fabs(a[t][c]) < eps) continue;

            for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);
            for (int i = n; i >= c; i--) a[r][i] /= a[r][c];
            for (int i = r + 1; i < n; i++)
                if (fabs(a[i][c]) > eps)
                    for (int j = n; j >= c; j--)
                        a[i][j] -= a[r][j] * a[i][c];

            r++;
        }
        // 至此 r 就是增广矩阵秩
        if (r < n)
        {
            for (int i = r; i < n; i++)
                if (fabs(a[i][n]) > eps)
                    return -1;
            return 1;
        }
        // 唯一解化为简化阶梯型矩阵
        // 只要保留第i行第i列的系数即可,所以从第i+1行开始一直消到第n行,
        // 因为只要结果,所以可以只消第i行第n+1列的数(b);
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                a[i][n] -= a[i][j] * a[j][n];
        return 0;
    }

    4.2. 高斯消元解异或方程组
    // a[N][N]是增广矩阵
    int gauss()
    {
        int r, c;
        for (r = 0, c = 0; c < n; c++)
        {
            int t = r;
            for (int i = r; i < n; i++)
                if (a[i][c])
                {
                    t = i;
                    break;
                }

            if (!a[t][c]) continue;

            for (int i = c; i <= n; i++) swap(a[r][i], a[t][i]);
            for (int i = r + 1; i < n; i++)
                if (a[i][c])
                    for (int j = n; j >= c; j--)
                        a[i][j] ^= a[r][j];

            r++;
        }

        if (r < n)
        {
            for (int i = r; i < n; i++)
                if (a[i][n])
                    return -1;
            return 1;
        }
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j <= n; j++)
                a[i][n] ^= a[i][j] & a[j][n];
        return 0;
    }

    4.3. 高斯消元解异或方程组(bitset优化)
    //bitset<N> a[N] 存增广矩阵, 时间复杂度为 O(n^3 / 32)
    int gauss()
    {
        int r, c;
        for (r = 0, c = 0; c < n; c++)
        {
            int t = r;
            for (int i = r; i < n; i++)
                if (a[i][c])
                {
                    t = i;
                    break;
                }

            if (!a[t][c]) continue;

            swap(a[r], a[t]);
            for (int i = r + 1; i < n; i++)
                if (a[i][c])
                    a[i] ^= a[r];

            r++;
        }

        if (r < n)
        {
            for (int i = r; i < n; i++)
                if (a[i][n])
                    return -1;
            return 1;
        }
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j <= n; j++)
                a[i][n] = a[i][n] ^ a[i][j] & a[j][n];
        return 0;
    }

5. 组合计数
    5.0. 组合数求法:
        5.0.1. 递推法:
               for (int i = 0; i < n; i++)
                   for (int j = 0; j <= i && j < k; j++)
                        if (!j) f[i][j][0] = 1; //第三维是高精度
                        else add(f[i][j], f[i - 1][j], f[i - 1][j - 1]);

        5.0.2. 分解质因数求解组合数
        // 比较适用于高精度, 也适用于模数 p 没有逆元的情况;
        // 令N = max(n, m), 则时间复杂度为:
        // O (筛质数(N) + 计算每个质数在阶乘中出现次数(N) + 每个质数出现的次数(最多为n) 之和sum{pi ^ [(n - 1) / (pi - 1)](pi <= n)});
        // 因此, 时间复杂度为 O(n), 用高精度(无快速幂)则为 O(n * loglogn * 一次乘法所需时间)

        // n, m 是int范围, n >= m >= 0 ;
        int get(int n, int p)
        {
            int ans = 0;
            while (n) ans += n / p, n /= p;
            return ans;
        }

        int C(int n, int m)
        {
            int ans = 1;
            for (int i = 1; i <= cnt; i++)
            {
                int p = prime[i];
                int s = get(n, p) - get(m, p) - get(n - m, p);
                ans = (ll)ans * qmi(p, s) % mod;
            }
            return ans;
        }

        // 高精度版本
        int get(int n, int p)
        {
            int ans = 0;
            while (n) ans += n / p, n /= p;
            return ans;
        }

        vector<int> C(int n, int m)
        {
            vector<int> ans;
            ans.push_back(1);
            for (int i = 1; i <= cnt; i++)
            {
                int p = prime[i];
                int s = get(n, p) - get(m, p) - get(n - m, p);
                while (s--) ans = mul(ans, p);
            }
            return ans;
        }

        5.0.2. 快速幂:
        5.0.3. 线性预处理逆元:

    5.1. 递推法
        长度为 n 的 01 序列, 每个位置可以任取 0 或 1, 要求相邻两个 1 之间隔着至少 k 个 0
        求合法的序列数：
        设 f[i] 为最后一个 1 在 位置i 的所有合法序列数,
        则 f[i] = f[0] + f[1] + f[2] + ... + f[i - k - 1] (f[0] = 1)

    5.2. 隔板法
        5.2.1. 等式
        5.2.2. 不等式

    5.3. 卡特兰数列
    给定 n 个 0 和 n 个 1，它们按照某种顺序排成长度为 2n 的序列，满足任意前缀中 0 的个数都不少于 1 的个数的序列数量为:
    Cat(n) = C(2n, n) / (n + 1) = C(2n, n) - C(2n, n - 1);
        以下问题都与Catalan数有关
        5.3.1.  n 个左括号和 n 个右括号形成的合法括号序列数量为Cat(n)
        5.3.2.  1,2,...,n 经过一个栈,形成的合法出栈序列数量为Cat(n)
        5.3.3.  n 个节点构成构成的不同二叉树的数量为 Cat(n)
        5.3.4.  在平面直角坐标系上, 每一步只能向上或向右走, 从 (0, 0) 走到 (n, n) 并且除两个端点外不接触直线 y = x 的路线数量为 2 * Cat(n) + 1

6. 容斥原理    
    6.1 多重集组合数
    从多重集 S = {A1*B1, A2*B2, ..., An*Bn} (Bi多重集中元素, Ai该元素数量)中选 M 个元素能够产生的不同多重集的数量:
    ans = C(N + M - 1, N - 1) - 
          SUM{C(N + M - Ai - 2, N - 1)|1<=i<=N} + 
          SUM{C(N + M - Ai - Aj - 3, N - 1)|1<=i<j<=N} - 
          ... +
          (-1)^N * C(N + M - SUM{Ai|1<=i<=N} - (N+1), N - 1);

    6.2 求 1~x 中与 n 互质的数个数
        //O( 2^(n的不同质因子个数) )
        void get(int n)
        {
            m = 0;
            for (int i = 2; (ll)i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    prime[++m] = i;
                    while (n % i == 0) n /= i;
                }
            }
            if (n > 1) prime[++m] = n;
        }

        ll solve(ll x)
        {
            ll ans = 0;
            for (int i = 0; i < 1 << m; i++)
            {
                int sgn = 1;
                ll val = 1;
                for (int j = 0; j < m; j++)
                {
                    if (i >> j & 1)
                    {
                        sgn *= -1;
                        val *= prime[j + 1];
                    }
                }
                ans += sgn * x / val;
            }
            return ans;
        }

    6.3. Mobius
        6.3.1. 线性筛 1~N 每一项 Mobius 函数
        // 线性筛法，求莫比乌斯函数, by yxc
        void init(int n)
        {
            mobius[1] = 1;
            for (int i = 2; i <= n; i ++ )
            {
                if (!st[i])
                {
                    primes[cnt ++ ] = i;
                    mobius[i] = -1;
                }
                for (int j = 0; primes[j] * i <= n; j ++ )
                {
                    int t = primes[j] * i;
                    st[t] = true;
                    if (i % primes[j] == 0)
                    {
                        mobius[t] = 0;
                        break;
                    }
                    mobius[t] = mobius[i] * -1;
                }
            }
        }
        // by lyl
        void mobius(int n)
        {
            memset(v, 0, sizeof(v));
            m = 0;
            miu[1] = 1;
            for (int i = 2; i <= n; i++)
            {
                if (!v[i])
                {
                    v[i] = i, prime[++m] = i;
                    miu[i] = -1;
                }
                for (int j = 1; j <= m; j++)
                {
                    if (prime[j] > v[i] || prime[j] * i > n) break;
                    v[prime[j] * i] = prime[j];
                    miu[prime[j] * i] = miu[i] * (i % prime[j] ? -1 : 0);
                }
            }
        }


        6.3.2. 求1<=x<=a, 1<=y<=b, (x, y) = 1, 的二元组<x,y>的对数
        // sum[i] = miu[1] + miu[2] + ... + miu[i];
        int n = min(a, b);
        ll ans = 0;
        for (int l = 1, r = 0; l <= n; l = r + 1)
        {
            int t1 = a / l, t2 = b / l;
            r = min(n, min(a / t1, b / t2));
            ans += (ll)t1 * t2 * (sum[r] - sum[l - 1]);
        }
        cout << ans << endl;

7. 概率与数学期望


8. 博弈论


9. 数论分块
    9.0. 向下向上取整转化:
    ⌈m/i⌉=⌊(m+i-1)/i⌋=⌊(m-1)/i⌋+1

    9.1. SUM{ down(m/i) | 1 <= i <= n}
    //
    int ans = 0;
    for (int l = 1, r = 0; l <= n; l = r + 1)
    {
        int t = m / l;              //块的值为t
        if (t) r = min(m / t, n);   //t != 0时，块右端点是n / t
        else r = n;                 //t == 0时，块右端点特判为n（即末尾）
        ans += (r - l + 1) * t;
    }

    9.2. SUM{ down(a/i) * down(b/i) | 1 <= i <= n }
        9.2.1 冗余版
        // n 为任意正整数, 可能大于 min(a, b)
        ll ans = 0;
        for (int l = 1, r = 0; l <= n; l = r + 1)
        {
            int t1 = a / l, t2 = b / l;
            if (t1 && t2) r = min(n, min(a / t1, b / t2));
            else if (t1) r = min(n, a / t1);
            else if (t2) r = min(n, b / t2);
            else r = n;
            ans += (ll)(r - l + 1) * t1 * t2;
        }
        9.2.2 简练版
        // n 不大于 min(a, b)
        ll ans = 0;
        for (int l = 1, r = 0; l <= n; l = r + 1)
        {
            int t1 = a / l, t2 = b / l;
            r = min(n, min(a / t1, b / t2));
            ans += (ll)(r - l + 1) * t1 * t2;
        }



二、基本算法
2. 三分 O(1.7logn)
    2.1. 整数三分
    //
    int l = 1, r = 10000000;
    while(l < r) 
    {
        int lmid = l + (r - l) / 3;
        int rmid = r - (r - l) / 3;
        lans = f(lmid), rans = f(rmid);
         // 求凹函数的极小值
        if(lans <= rans) r = rmid - 1;
        else l = lmid + 1;
        // 求凸函数的极大值
        if(lasn >= rans) l = lmid + 1;
        else r = rmid - 1;
    }
    printf("%.6f\n", f(l));

    2.2. 实数三分
    //直接循环上1000次,可能要比 r - l < eps 更优
    const double eps = 1e-9;
    while(r - l < eps)
    {
        double lmid = l + (r - l) / 3;
        double rmid = r - (r - l) / 3;
        lans = f(lmid),rans = f(rmid);
        // 求凹函数的极小值
        if(lans <= rans) r = rmid;
        else l = lmid;
        // 求凸函数的极大值
        if(lans >= rans) l = lmid;
        else r = rmid;
    }
    // 输出 l 或 r 都可
    cout << l << endl;

3. 高精度
    3.1. 加法:
        // C = A + B, A >= 0, B >= 0
        vector<int> add(vector<int> &A, vector<int> &B)
        {
            if (A.size() < B.size()) return add(B, A);

            vector<int> C;
            int t = 0;
            for (int i = 0; i < A.size(); i ++ )
            {
                t += A[i];
                if (i < B.size()) t += B[i];
                C.push_back(t % 10);
                t /= 10;
            }

            if (t) C.push_back(t);
            return C;
        }

    3.2. 减法:
        // C = A - B, 满足A >= B, A >= 0, B >= 0
        vector<int> sub(vector<int> &A, vector<int> &B)
        {
            vector<int> C;
            for (int i = 0, t = 0; i < A.size(); i ++ )
            {
                t = A[i] - t;
                if (i < B.size()) t -= B[i];
                C.push_back((t + 10) % 10);
                if (t < 0) t = 1;
                else t = 0;
            }

            while (C.size() > 1 && C.back() == 0) C.pop_back();
            return C;
        }

    3.3. 乘法:
        3.3.1 高精度 * 低精度:
        // C = A * b, A >= 0, b >= 0
        vector <int> mul(vector <int> & A, int b) {
            vector <int> C;

            int t = 0;
            for (int i = 0; i < A.size(); i ++) {
                t += A[i] * b;       // t + A[i] * b = 7218
                C.push_back(t % 10); // 只取个位 8
                t /= 10;             // 721 看作 进位
            }

            while (t) {            // 处理最后剩余的 t
                C.push_back(t % 10);
                t /= 10;
            }

            while (C.size() > 1 && C.back() == 0) C.pop_back();

            return C;
        }

        3.3.2 高精度 * 高精度:
        vector<int> mul(vector<int> &A, vector<int> &B) {
            vector<int> C(A.size() + B.size(), 0); // 初始化为 0，且999*99最多 5 位

            for (int i = 0; i < A.size(); i++)
                for (int j = 0; j < B.size(); j++)
                    C[i + j] += A[i] * B[j];

            int t = 0;
            for (int i = 0; i < C.size(); i++) { // i = C.size() - 1时 t 一定小于 10
                t += C[i];
                C[i] = t % 10;
                t /= 10;
            }

            while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
            return C;
        }

    3.4. 除法 (高精除以低精)
        // A / b = C ... r, A >= 0, b > 0
        vector<int> div(vector<int> &A, int b, int &r)
        {
            vector<int> C;
            r = 0;
            for (int i = A.size() - 1; i >= 0; i -- )
            {
                r = r * 10 + A[i];
                C.push_back(r / b);
                r %= b;
            }
            reverse(C.begin(), C.end());
            while (C.size() > 1 && C.back() == 0) C.pop_back();
            return C;
        }