数论

板子

---

快速幂

const LL MOD = 1000000007;
// 求res 的n 次方对MOD 取模
LL fast_pow(LL res, LL n) {
    LL ans;
    for(ans = 1; n != 0; n >>= 1) {
        if(n % 2 == 1) ans = (ans * res) % MOD;
        res = (res * res) % MOD;
    }
    return ans;
}

逆元预处理 + Lucas 定理

const LL MOD = 1e9 + 7;
const int maxn = 1e6 + 100;
LL inv[maxn], pro[maxn], invpro[maxn];
// maxn 为所求数字上界，当n 和m 大于MOD 时，需要用到Lucas 函数
// 否则只要直接get_C 函数即可
void Prepare_C() {
    inv[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        inv[i] = (LL)(MOD - MOD / i) * inv[MOD % i] % MOD;
    }
    pro[0] = invpro[0] = 1;
    for(int i = 1; i < maxn; ++i) {
        pro[i] = pro[i - 1] * i % MOD;
        invpro[i] = invpro[i - 1] * inv[i] % MOD;
    }
}
LL get_C(int n, int m) {
    if(n < m) {
        return 0;
    }
    return pro[n] * invpro[m] % MOD * invpro[n - m] % MOD;
}
LL Lucas(LL n, LL m) {
    if(n < MOD && m < MOD) {
        return get_C(n, m);
    }
    LL tmp = get_C(n % MOD, m % MOD);
    if(tmp == 0) {
        return 0;
    }
    return tmp * Lucas(n / MOD, m / MOD) % MOD;
}

埃氏素数（HDU 1164）

const int maxn = 100000 + 100;
int n, cnt;
int prime[maxn];
bool vis[maxn];
void Prime() {
    for(int i = 2; i < maxn; ++i) {
        if(!vis[i]) {
            prime[cnt++] = i;
            for(int j = i; j < maxn / i; ++j) {
                vis[i * j] = true;
            }
        }
    }
}

欧拉筛素数/欧拉函数/莫比乌斯函数打表（HDU 2841）

const int maxn = 100000 + 100;
int cnt;
int prime[maxn], mu[maxn], phi[maxn];
bool vis[maxn];
// prime 下标范围为 [0, cnt)
// phi 为欧拉函数，mu 为莫比乌斯函数
// vis[i] 为 false 表示 i 是质数
// 调用时 n 需小于 maxn
void Prime(int n) {
    mu[1] = 1;
    phi[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!vis[i]) {
            prime[cnt++] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for(int j = 0; j < cnt && i <= n / prime[j]; ++j) {
            int k = i * prime[j];
            vis[k] = true;
            if(i % prime[j] == 0) {
                mu[k] = 0;
                phi[k] = phi[i] * prime[j];
                break;
            } else {
                mu[k] = -mu[i];
                phi[k] = phi[i] * (prime[j] - 1);
            }
        }
    }
}

$\sqrt n$ 分解质因数

void get_fac(LL n, vector<pair<LL, int> > &p) {
    for(int i = 0; i < cnt && prime[i] <= n / prime[i]; ++i) {
        if(n % prime[i] == 0) {
            p.push_back(make_pair(prime[i], 0));
            while(n % prime[i] == 0) {
                ++p.back().second;
                n /= prime[i];
            }
        }
    }
    if(n != 1) {
        p.push_back(make_pair(n, 1));
    }
}

gcd(n, m) = d 的对数（HDU 1695）

// 求从 1 到 n 和 1 到 m 之间有多少个有序对 (a, b) 满足 gcd(a, b) = d
// 时间复杂度 O(sqrt(min(n, m) / d))
// sum 为莫比乌斯函数前缀和
LL F(int n, int m, int d) {
    if(n > m) {
        swap(n, m);
    }
    LL ret = 0;
    n /= d;
    m /= d;
    int last = 1;
    for(int i = 1; i <= n; i = last + 1) {
        last = min(n / (n / i), m / (m / i));
        ret += (LL)(sum[last] - sum[i - 1]) * (n / i) * (m / i);
    }
    return ret;
}

√n求解欧拉函数

int euler(int n) {
    if(n == 1) return 1;
    int ret = n;
    for(int j = 0; j < cnt && prime[j] * prime[j] <= n; ++j) {
        if(n % prime[j] == 0) {
            ret = ret / prime[j] * (prime[j] - 1);
            while(n % prime[j] == 0) n /= prime[j];
        }
    }
    if(n > 1) ret = ret / n * (n - 1);
    return ret;
}

矩阵快速幂

const int matrix_size = 10;
const int MOD = 1000000007;
int add(int a, int b) {
    a += b;
    if(a >= MOD) {
        return a - MOD;
    }
    return a;
}
struct Matrix {
    int size;
    int num[matrix_size][matrix_size];
    void operator=(const Matrix &m) {
        for(int i = 0; i < size; ++i) {
            memcpy(num[i], m.num[i], sizeof(int) * size);
        }
    }
    void Init() {
        for(int i = 0; i < size; ++i) {
            memset(num[i], 0, sizeof(int) * size);
            num[i][i] = 1;
        }
    }
    void Set(int s) {
        size = s;
        // codes...
    }
    void operator*=(const Matrix &m) {
        static Matrix ans;
        ans.size = size;
        for(int i = 0; i < size; ++i) {
            for(int j = 0; j < size; ++j) {
                ans.num[i][j] = 0;
                for(int k = 0; k < size; ++k) {
                    ans.num[i][j] = add(ans.num[i][j], (LL)num[i][k] * m.num[k][j] % MOD);
                }
            }
        }
        (*this) = ans;
    }
    void fast_pow(LL n) {
        static Matrix ans;
        ans.size = size;
        for(ans.Init(); n != 0; n >>= 1) {
            if((n & 1) == 1) {
                ans *= (*this);
            }
            (*this) *= (*this);
        }
        (*this) = ans;
    }
};

exgcd（cal 函数求ax + by = c 的最小非负整数解）

void exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if(b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        exgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}
void cal(LL a, LL b, LL c, LL &x, LL &y) {
    LL gcd;
    exgcd(a, b, gcd, x, y);
    if(c % gcd != 0) {
        x = -1;
        return ;
    }
    x *= c / gcd;
    LL mod = abs(b / gcd);
    x = (x % mod + mod) % mod;
    y = (c - a * x) / b;
}

中国剩余定理

// 下标范围为 [0, len)
LL CRT(LL *r, LL *m, int len) {  // r Remain m MOD
    LL M = m[0];
    LL ret = r[0];
    LL d, x, y;
    for(int i = 1; i < len; ++i) {
        exgcd(M, m[i], d, x, y);
        if((r[i] - ret) % d) {
            return -1;          // 判断是否有解，无解返回 -1
        }
        x = (r[i] - ret) / d * x % (m[i] / d);
        ret += x * M;
        M = M / d * m[i];
        ret %= M;
    }
    ret = (ret + M) % M;
    return ret == 0? M: ret;
}

数位dp

int a[100];
LL dp[20][2];
LL dfs(int pos, int stat, bool limit) {
    if(pos == -1) {
        return stat;
    }
    if(!limit && dp[pos][stat] != -1) {
        return dp[pos][stat];
    }
    int up = limit? a[pos]: 9;
    LL ans = 0;
    for(int i = 0; i <= up; ++i) {
        ans += dfs(pos - 1, stat | (i == 6? 1: 0), limit && i == a[pos]);
    }
    if(!limit) {
        dp[pos][stat] = ans;
    }
    return ans;
}
LL solve(LL x) {
    int pos = 0;
    while(x != 0) {
        a[pos++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1, 0, true);
}

反素数

// depth 表示搜索到第 depth 个素数，素数下标范围为 [0, cnt)，Count 为约数个数，up 为下一个素数指数最大值+1，ans 为 n 以最大反素数约数个数
void dfs(int depth, LL Count, LL Num, int up) {
    ans = max(ans, Count);
    if(depth == cnt || Num > n / prime[depth]) {
        return ;
    }
    for(int i = 1; i < up && Num <= n / prime[depth]; ++i) {
        Num *= prime[depth];
        dfs(depth + 1, Count * (i + 1), Num, i + 1);
    }
}

Catalan 数

令：$h_0=1,h_1=1$，则 $Catalan$ 数满足递推式：

$$h_n=\sum_{i=0}^{n-1}h_i\times h_{n-1-i}\quad(n>=2)$$
其通项为：
$$h_n=\frac{C_{2n}^n}{n+1}\quad(n=0,1,2,\cdots)$$

Catalan 数相关结论

$n$ 个数的出栈、入栈方案数
$n$ 对括号的匹配方案数
$n$ 个节点构成的二叉树种数
圆上 $2n$ 个点，两两连线不相交的情况数
一个 $n+2$ 边形，分割成多个三角形的方案数

直角三角形三边长为整数的可能斜边长 $c$

将 $c$ 分解质因数后，统计其质因数对 $4$ 取模等于 $1$ 的个数，若个数大于 $0$，则满足条件。

斯特林近似

斯特林近似用于求解 $n!$ 的近似值：

$$n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$