来自算法基础课

质数

判断一个数是不是质数 $O(\sqrt{n})$

bool is_prime(int x){
    if(x < 2)
        return false;
    for(int i = 2; i <= x / i; i ++)
        if(x % i == 0)
            return false;
    return true;
}

分解质因数 $O(\sqrt{n})$

void divide(int x){
    for(int i = 2; i <= x / i; i ++){
        if(x % i == 0){
            int c = 0;
            while(x % i == 0){
                x /= i;
                c ++;
            }
            printf("%d %d\n", i, c);
        }
    }
    if(x > 1)
        printf("%d 1\n", x);
    putchar('\n');
}

线性筛质数 $O(n)$

int primes[N], st[N];
int cnt;

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i])
            primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
                break;
        }
    }
}

约数

试除法求约数 $O(\sqrt{n})$

vector<int> get_divison(int x){
    vector<int> res;
    for(int i = 1; i <= x / i; i ++)
        if(x % i == 0){
            res.push_back(i);
            if(i != x / i)
                res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

约数个数

不妨设$x=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}$ ($p_1$,$p_2$,……,$p_n$都为质数且互不相同)
则$x$的约数个数为
$(\alpha_1+1) (\alpha_2+1) \cdots (\alpha_n+1)$

约数之和

不妨设$x=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}$ ($p_1$,$p_2$,……,$p_n$都为质数且互不相同)
则$x$的约数之和为
$(p_1^0+p_1^1+p_1^2+\cdots+p_1^{\alpha_1}) (p_2^0+p_2^1+p_2^2+\cdots+p_2^{\alpha_2}) \cdots (p_n^0+p_n^1+p_n^2+\cdots+p_n^{\alpha_n})$也就是$\dfrac{p_1^{\alpha_1+1}-1}{p_1-1} \dfrac{p_2^{\alpha_2+1}-1}{p_2-1} \cdots \dfrac{p_n^{\alpha_n+1}-1}{p_n-1}$(运用等比数列求和公式)

最大公约数 $O(logn)$

不妨设$a≥b$
$gcd(a,b)=gcd(b,a \, mod \, b)$

欧拉函数

欧拉函数的定义

定义$\varphi(x)=$$1$~$x$中的与$x$互质的数
不妨设$x=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}$ ($p_1$,$p_2$, $\cdots$ ,$p_n$都为质数且互不相同)
则$\varphi(x)=x (1-\frac{1}{p_1}) (1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_n})$

求一个数的欧拉函数 $O(\sqrt{n})$

运用公式即可

int phi(int x){
    int res = x;
    for(int i = 2; i <= x / i; i ++)
        if(x % i == 0){
            res = res / i * (i - 1);
            while(x % i == 0)
                x /= i;
        }
    if(x > 1)
        res = res / x * (x - 1);
    return res;
}

求$1$~$n$中的所有数的欧拉函数 $O(n)$

int primes[N], phi[N], st[N];
int cnt = 0;

void get_euler(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i ++){
        if(!st[i]){
            primes[cnt ++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0){
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}

快速幂

快速幂 (求$a^b \, mod \,p$) $O(logb)$

long long quick_pow(long long a, long long b, long long p){
    long long res = 1 % p;
    while(b){
        if(b & 1)
            res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

快速幂求逆元 (前提是$p$为质数)

$a^{-1} \equiv a^{p-2} (mod \, p)$ (运用$Fermat$小定理)
用快速幂即可

扩展欧几里得算法

$Bezout$定理 $ax+by=gcd(a,b)$一定有正整数解$(x,y)$

请看这个分享

扩展欧几里得算法的证明 $O(log(b))$

这个算法求的是$ax+ by=gcd(a,b)$的一个解$(x,y)$
当$b=0$时，原方程等价于求$ax=a$的一个解$(x,y)$,取$x=1$,$y=0$即可
当$b>0$时，设$d=gcd(a,b)$,在递归中，我们已经算出$(a \, mod \, b)y_0+bx_0=d$的一组解$(x_0,y_0)$
等价于求$(a \, mod \, b)x_0+by_0=ax+by$的解$(x,y)$,结合$a \, mod \, b=a-b[\frac{a}{b}]$ => $ax_0-[\frac{a}{b}]bx_0+by_0=ax+by$=> $ax_0+b(y_0-[\frac{a}{b}]x_0)=ax+by$ => 取$x=x_0$,$y=y_0-[\frac{a}{b}]x_0$即可

int exgcd(int a, int b, int& x, int& y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

扩展欧几里得算法求解线性同余方程

由$Bezout$定理，可知方程$ax+by=c$有解当且仅当$gcd(a,b)|c$
此时可以用扩展欧几里得算法求出方程$ax+by=gcd(a,b)$的一组解，然后两边同时乘$(c÷gcd(a,b))$即可

中国剩余定理

$∀i=1$~$n$,都有$x≡a_i(mod m_i)$,($m_1$,$m_2$, $\cdots$ ,$m_n$两两互质), 求$x$
设$M$=$a_1a_2……a_n$ ，$∀i=1$~$n$,$M_i=\frac{M}{a_i}$,$M_i^{-1}为M_i mod m_i的逆$
则$x$的最小值为$[(a_1M_1M_1^{-1}) + (a_2M_2M_2^{-1}) + …… + (a_nM_nM_n^{-1})] \,mod \,M$

中国剩余定理的证明

只需证明$∀i=1$~$n$,都有$x≡a_i(mod \, m_i)$即可
不妨考虑$i=1$的情况
$i=1$时，$x=[(a_1M_1M_1^{-1}) + (a_2M_2M_2^{-1}) + …… + (a_nM_nM_n^{-1})] \,mod \,M$

$=[(a_1M_1M_1^{-1}) + (a_2M_2M_2^{-1}) + …… + (a_nM_nM_n^{-1})]-kM$

$=[(a_1M_1M_1^{-1}) + (a_2M_2M_2^{-1}) + …… + (a_nM_nM_n^{-1})]-kM_1a_1$

$≡(a_1M_1M_1^{-1}) + (a_2M_2M_2^{-1}) + …… + (a_nM_nM_n^{-1}) \, (mod \, m_1)$

结合$M_2$,$M_3$,$M_4$,……,$M_n$ = $m_1k_2$,$m_1k_3$,……,$m_1k_n$, $M_1M_1^{-1} ≡ 1(mod \,m_1)$
=> $x \equiv a_1 + a_2m_1k_2 + a_3m_1k_3 + …… + a_nm_1k_n \equiv a_1 (mod \, m_1)$
同理,$i=2$, $i=3$, $\cdots$ $i=n$时同样成立
综上所述，中国剩余定理得证

用中国剩余定理求解线性同余方程组

LL exgcd(LL a, LL b, LL& x, LL& y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main(){
    bool has_answer = true;
    int n;
    scanf("%d", &n);
    LL a1, a2, m1, m2;
    scanf("%lld %lld", &a1, &m1);
    while(-- n){
        scanf("%lld %lld", &a2, &m2);
        LL k1, k2;
        LL d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d != 0){
            has_answer = false;
            break;
        }
        k1 *= (m2 - m1) / d;
        LL t = a2 / d;
        k1 = (k1 % t + t) % t;
        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2);
    }
    if(has_answer)
        printf("%lld\n", (m1 % a1 + a1) % a1);
    else
        puts("-1");
    return 0;
}

高斯消元 $O(n^3)$

高斯消元求解线性方程组

1. 找到这一列中绝对值最小的数
2. 将这一行和绝对值最小的数所在的行交换
3. 将这一行中的第一个非0的数变为1
4. 将这一列下面所有的数消成0
5. 如果最后的方程不足$n$个
   1. 如果出现了$0x_i≠0$
      就说明出现了矛盾（无解）
   2. 否则
      就说明没有矛盾（有无穷多组解）
6. 否则这个方程组就一定有唯一解
   就要倒着推出$x_n$,$x_{n-1}$, $\cdots$ ,$x_1$

int gauss(){
    int c = 0, r = 0;
    for(; c < n; c ++){
        int t = r;
        for(int i = r + 1; i < n; i ++)
            if(abs(a[i][c]) > abs(a[t][c]))
                t = i;
        if(abs(a[t][c]) < eps)
            continue;
        for(int i = c; i < n + 1; 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(abs(a[i][c]) > eps)
                for(int j = n; j >= c; j --)
                    a[i][j] -= a[r][j] * a[i][c];
        r ++;
    }
    if(r < n){
        for(int i = 0; i < n; i ++)
            if(abs(a[i][n]) < eps)
                return 1; // 无解
        return 2; // 有无穷多组解
    }
    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; // 有唯一解
}

高斯消元求解异或线性方程组

1. 找到这一列中非0的数
2. 将这一行和非0的数所在的行进行交换
3. 将这一行下面所有的数都消成0
4. 如果最后的方程不足$n$个
   1. 如果出现了$0x_i≠0$
      就说明出现了矛盾（无解）
   2. 否则
      就说明没有矛盾（有无穷多组解）
5. 否则这个方程组就一定有唯一解
   就要倒着推出$x_n$,$x_{n-1}$, $\cdots$ ,$x_1$

int gauss(){
    int r = 0, c = 0;
    for(; c < n; c ++){
        int t = r;
        for(int i = r; i < n + 1; i ++)
            if(a[i][c])
                t = i;
        if(!a[t][c])
            continue;
        for(int i = c; i < n + 1; i ++)
            swap(a[t][i], a[r][i]);
        for(int i = r + 1; i < n; i ++)
            if(a[i][c])
                for(int j = c; j <= n; j ++)
                    a[i][j] ^= a[r][j];
        r ++;
    }
    if(r < n){
        for(int i = r; i < n; i ++)
            if(a[i][n])
                return 2;
        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;
}

求组合数

用递推求组合数 $mod 1e9+7$ $O(n^2)$

中心思想：$C(a,b)=C(a-1,b)+C(a-1,b-1)$

for(int i = 0; i <= Max_N; i ++)
        for(int j = 0; j <= i; j ++)
            if(j == 0)
                C[i][j] = 1;
            else
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % Mod;

用预处理阶乘和阶乘的逆元求组合数 $mod \, 1e9+7$ $O(nlog(Mod))$

中心思想：$C(a,b)=a!÷b!÷(a-b)!$ (由于求逆元时用了$Fermat$小定理，所以要求$Mod$为质数)

int fact[N], infact[N];

int quick_pow(int a, int b, int p){
    int res = 1 % p;
    while(b){
        if(b & 1)
            res = (LL)res * a % p;
        b >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

void init(){
    fact[0] = infact[0] = 1;
    for(int i = 1; i <= 1e5; i ++){
        fact[i] = (LL)fact[i - 1] * i % Mod;
        infact[i] = (LL)infact[i - 1] * quick_pow(i, Mod - 2, Mod) % Mod;
    }
}

int C(int a, int b){
    return (LL)fact[a] * infact[b] % Mod * infact[a - b] % Mod;
}

用Lucas定理求组合数 $mod \,p$的值 $O(plog(a/p)log(p))$

中心思想：$$C(a,b) \equiv C(a \,mod \,p,b \,mod \,p) \times C([\frac{a}{p}],[\frac{b}{p}]) (mod \,p)$$ ($p$为质数)

Lucas定理的证明

设$a=(a_kp^k) + (a_{k-1}p^{k-1}) + …… + (a_0p^0)$,$b=(b_kp^k) + (b_{k-1}p^{k-1}) + …… + (b_0p^0)$

$(1+x)^p = (C(p, 0)x^0) + (C(p, 1)x^1) + …… + (C(p, p)x^p)$
又$p$为质数 => $p|C(p,i)$ ($0<i<n$)

$(1+x)^p ≡ C(p,0)1 + C(p,p)x^p = 1+x^p (mod p)$
$(1+x)^{p^k} ≡ (1+x^p)^k (mod p)$
$(1+x)^a = (1+x)^{a_0} [(1+x)^p]^{a_1} [(1+x)^{p^2}]^{a_2} …… [(1+x)^{p^k}]^{a_k}$
$(1+x)^a ≡ (1+x)^{a_0} (1+x^p)^{a_1} (1+x^{p^2})^{a_2} …… (1+x^{p_k})^{a_k} (mod \, p)$

现在考察同余式两边$x^b$的常数
=> $$C(a,b) ≡ C(a_k, b_k) C(a_{k-1},b_{k-1}) …… C(a_0,b_0)= C(a \,mod \,p,b \,mod p) C(\frac{a}{p},\frac{b}{p}) (mod p)$$
$a=(a_kp^k) + (a_{k-1}p^{k-1}) + …… + (a_0p^0) = C(a \,mod \,p,b \,mod \,p) C([\frac{a}{p}], [\frac{b}{p}]) (mod p)$

LL quick_pow(LL a, LL b, LL p){
    LL res = 1;
    while(b){
        if(b & 1)
            res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

LL C(LL a, LL b, LL p){
    LL res = 1;
    for(int i = 1, j = a; i <= b; i ++, j --){
        res = res * j % p;
        res = res * quick_pow(i, p - 2, p) % p;
    }
    return res;
}

LL lucas(LL a, LL b, LL p){
    if(a < p && b < p)
        return C(a, b, p);
    else
        return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

用分解质因数求组合数(高精度)

int primes[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i])
            primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
                break;
        }
    }
}

int get(int n, int p){
    int res = 0;
    while(n){
        res += n / p;
        n /= p;
    }
    return res;
}

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;
        c.push_back(t % 10);
        t /= 10;
    }
    while(t){
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main(){
    int a, b;
    scanf("%d %d", &a, &b);
    get_primes(a);
    for(int i = 0; i < cnt; i ++){
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }
    vector<int> res;
    res.push_back(1);
    for(int i = 0; i < cnt; i ++)
        for(int j = 0; j < sum[i]; j ++)
            res = mul(res, primes[i]);
    for(int i = res.size() - 1; i >= 0; i --)
        printf("%d", res[i]);
    return 0;
}

求Catalan数

公式：$Cat_n = \frac{C(2n,n)}{(n+1)}$

容斥原理

$$|S_1∪S_2∪S_3∪\cdots∪S_n| = (|S_1|+|S_2|+|S_3|+\cdots+|S_n|) - (|S_1∩S_2|+|S_1∩S_3|+\cdots+|S_{n-1}∩S_n|) + \cdots $$

容斥原理的证明

只需证：$∀x∈S_i$都有$C(k,1)-C(k,2)+C(k,3)-……+(-1)^kC(k,k)=1$即可
$C(k,1)-C(k,2)+C(k,3)-……+(-1)^kC(k,k)=1$ <=> $-(1-1)^k+C(k,0)=1$,这是显然的
综上所述，容斥原理得证

用容斥原理求$1$~$n$中可以被$a_1$, $a_2$, ……, $a_n$整除的数的个数n $O(m2^m)$

for(int i = 1; i < 1 << m; i ++){
    int s = 0;
    long long t = 1;
    for(int j = 0; j < m; j ++)
        if(i >> j & 1){
            s ++;
            if((long long) t * a[j] > n){
                t = -1;
                break;
            }
            t *= a[j];
        }
    if(t != -1)
        if(s % 2)
            res += n / t;
        else
            res -= n / t;
}

博弈论

Nim游戏

如果$a_1 \,Xor \,a_2 \,Xor \, \cdots \,Xor \,a_n = 0$
则先手必败
否则
先手必胜

台阶-Nim游戏

相当于在奇数级台阶上玩Nim游戏

集合-Nim游戏

int s[N], f[M];
int res = 0;

int sg(int x){
    if(f[x] != -1)
        return f[x];
    unordered_set<int> S;
    for(int i = 0; i < m; i ++)
        if(x >= s[i])
            S.insert(sg(x - s[i]));
    for(int i = 0; ; i ++)
        if(!S.count(i))
            return f[x] = i;
}

// main函数中
while(n --){
    int x;
    scanf("%d", &x);
    res ^= sg(x);
}

拆分-Nim游戏

int s[N], f[M];
int res = 0;

int sg(int x){
    if(f[x] != -1)
        return f[x];
    unordered_set<int> S;
    for(int i = 0; i < x; i ++)
        for(int j = 0; j <= i; j ++)
            S.insert(sg(i) ^ sg(j));
    for(int i = 0; ; i ++)
        if(!S.count(i))
            return f[x] = i;
}

// main函数中
while(n --){
    int x;
    scanf("%d", &x);
    res ^= sg(x);
}