跳转至

数学

最大公约数 最小公倍数 唯一分解定理

\(\gcd(a, b) = \gcd(b, a\%b)\)

// 1. 最大公约数（GCD）- 欧几里得算法（迭代版）
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

// 2. 最小公倍数（LCM）- 基于GCD计算
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0; // 0和任何数的最小公倍数是0
    return (a / gcd(a, b)) * b; // 先除后乘避免溢出
}

分解质因数 判定素数 素数筛

分解质因数

vector<int> primeFactorization(int n) {
    vector<int> factors;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

素数筛:使用素数的倍数去筛掉合数

但是一个合数会被多次素数筛除影响效率

bool isnp[MAXN]; // is not prime: 不是素数
void init(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (!isnp[i])
            for (int j = i * i; j <= n; j += i)
                isnp[j] = 1;
}

引入欧拉筛:不会重复筛除

合数只筛一次 保证是被最小质因数筛除

质数就需要遍历全部筛除

bool isnp[MAXN]; // 标记是否为合数
vector<int> primes; // 存储素数表

void euler_sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isnp[i]) primes.push_back(i); // i是素数，加入表
        for (int p : primes) { 
            if (p * i > n) break; // 超出范围，停止
            isnp[p * i] = true; // 标记p*i为合数
            if (i % p == 0) break; // 保证p是i的最小质因子，避免重复筛
        }
    }
}

快速幂

非递归快速幂

private static long powMod(long a, long b, long mod) {
    long result = 1;
    a %= mod; // 防止a过大
    while (b > 0) {
        if ((b & 1) != 0) result = (result * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return result;
}

矩阵快速幂

应用:①先根据题意求出递推公式 ②根据递推公式写出它的转移矩阵T，即TX^ (n-1)=X^ n。注意此转移矩阵的系数不包含未知数，这样才可以进行第③步 ③求出转移矩阵T后，TX^ (n-1)=X^ n，利用矩阵的快速幂求出X^(n-1)的值，最后乘以系数矩阵T（也称为转移矩阵）得出矩阵X ^ n的值

    private static long[][] multiply(long[][] a, long[][] b,int n,int mod){

        long[][] result = new long[80][80];
        for(int i=1;i<=2*n;i++){
            for(int j=1;j<=2*n;j++){
                for(int k=1;k<=2*n;k++){
                    result[i][j] += ((a[i][k]*b[k][j])%mod);
                    result[i][j] %=mod;
                }
            }
        }
        return result;
    }

    private static long[][] quick(int k,int n,int mod){

        long[][] cur = new long[80][80];
        long[][] result = new long[80][80];

        for(int i=1;i<=2*n;i++){
            result[i][i]=1;
        }
        cur = matrix;

        while(k!=0){
            if(k%2 ==1) result = multiply(result, cur, n, mod);
            cur = multiply(cur, cur, n, mod);
            k/=2; 
        }
        return result;
    }

exgcd

\(\gcd(a, 0) = a\)

\(ax_1 + by_1 = \gcd(a, b) =bx_2 + (a \bmod b)y_2 = \gcd(b, a \bmod b)\)

    static long x,y;
    public static long exgcd(long a,long b){
        if (b==0){
            x=1;
            y=0;
            return a;
        }
        long res=exgcd(b,a%b);
        long k=x;
        x=y;
        y=k-a/b*y;
        return res;
    }

逆元

费马小定理

对于整数 \(a\) 与正整数模 \(m\)，若 \(\gcd(a,m)=1\)，则在同余类环 \(\mathbb{Z}/m\mathbb{Z}\) 中存在唯一的 \(x\) 使得 \(a\,x \equiv 1 \pmod m.\) 这时称 \(x\) 是 \(a\) 关于模 \(m\) 的逆元，记为 \(x \equiv a^{-1}\pmod m.\)

若 a 与质数 p 互质\(a^{p-1} \equiv 1 \pmod{p}\)

也就是说，当模数为质数，且需要求逆元的数与模数互质时，可通过快速幂直接求取其逆元。

long long quickpow(long long a,long long n)
{
    a%=mod;
    long long res=1;
    while(n>0)
    {
        if(n&1) res=(res*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return res;
}
long long inv(long long a)
{
    return quickpow(a,mod-2);
}

exgcd求逆元

    public static long exgcd(long a,long b){
        if (b==0){
            x=1;
            y=0;
            return a;
        }
        long res=exgcd(b,a%b);
        long k=x;
        x=y;
        y=k-a/b*y;
        return res;
    }
    public static long invExgcd(long a,long p){
        long g=exgcd(a,p);
        if (g!=1) return -1;
        else return (x%p+p)%p;
    }

快速求多个逆元

int inv[1000000];
void find_inv(int last,int p)//求1~last所有数模p意义下的逆元
{
    inv[1]=1;//1的逆元就是1本身
    for(int i=2;i<=last;i++)
        inv[i]=(long long)(p-p/i)*(inv[p%i])%p;
    //注意longlong，否则有可能导致溢出
}

欧拉函数 欧拉降幂

数论中的欧拉函数 \(\varphi(x)\) 是一个非常重要的函数，它定义为小于（或不大于，这里是一样的）\(x\) 但与 \(x\) 互质的正整数的数量。例如\(\varphi(12)=4,\) 因为 \(1,5,7,11\) 与 \(12\) 互质。特别地，规定\(\varphi(1)=1.\) 对于欧拉函数，主要有如下性质：

  1. 若 \(p\) 是质数，则 \(\varphi\bigl(p^n\bigr)=p^{n-1}(p-1).\)
  2. 若 \(a\mid x\)，则 \(\varphi(a x)=a\,\varphi(x).\)
  3. 若 \(\gcd(a,b)=1\)，则 \(\varphi(a)\,\varphi(b)=\varphi(a b).\)

我们把正整数质因数分解： \(x = p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n}\) 所有 \(p_i^{k_i}\) 两两互质，由欧拉函数的性质有： \(\varphi(x) = p_1^{k_1 - 1}(p_1 - 1) \cdot p_2^{k_2 - 1}(p_2 - 1) \cdots p_n^{k_n - 1}(p_n - 1)\) 即： \(\varphi(x) = x \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdots \frac{p_n - 1}{p_n}\)

//理解模拟  慢
int phi(int n)
{
    int res = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            res = res / i * (i - 1); // 先除再乘防止溢出
        while (n % i == 0) // 每个质因数只处理一次，可以把已经找到的质因数除干净
            n /= i;
    }
    if (n > 1)
        res = res / n * (n - 1); // 最后剩下的部分也是原来的n的质因数
    return res;
}

int phi[MAXN];
void init(int n)
{
    for (int i = 1; i <= n; i++)
        phi[i] = i; // 除1外没有数的欧拉函数是本身，所以如果phi[i] = i则说明未被筛到
    for (int i = 2; i <= n; i++)
        if (phi[i] == i) // 未被筛到
            for (int j = i; j <= n; j += i) // 所有含有该因子的数都进行一次操作
                phi[j] = phi[j] / i * (i - 1);
}

void init(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i), phi[i] = i - 1; // 性质一，指数为1的情形
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
            {
                phi[p * i] = phi[i] * p; // 性质二
                break;
            }
            else
                phi[p * i] = phi[p] * phi[i]; // 这时肯定互质，用性质三
        }
    }
}

\(a^b \mod m = \begin{cases} a^{b \mod \varphi(m)} \mod m, & \gcd(a, m) = 1, \\ a^{b \mod \varphi(m) + \varphi(m)} \mod m, & \gcd(a, m) \neq 1 \ \text{且} \ b \geq \varphi(m), \\ a^b \mod m, & \text{其他情况}. \end{cases}\)

min25筛

杜教筛

排列组合 斯特林数

卡特兰数

\(H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}\)

\(H_n = \frac{H_{n-1} (4n-2)}{n+1}\)

\(H_n = \binom{2n}{n} - \binom{2n}{n-1}\)