最近考试经常考数学，但是我还没有整理过全部的板子，c不了，顺便考前熟悉一下。

质数 / 素数

O(n)O(\sqrt n) 判断素数

1
2
3
4
5
6
7
bool check(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++)
        if (x % i == 0) return false;
    return true;
}

O(nlog⁡log⁡n)O(n \log \log n) 埃拉托尼斯筛法

1
2
3
4
5
6
7
8
9
10
11
12
bool vis[N];
int primes[N], cnt;

void Eratosthenes(int N)
{
    for (int i = 2; i <= N; i ++)
    {
        if (!vis[i]) primes[++ cnt] = i;
        else for (int j = i << 1; j <= N; j += i)
            vis[j] = true;
    }
}

O(n)O(n) 欧拉筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool vis[N];
int primes[N], cnt;

void Euler_Prime(int N)
{
    for (int i = 2; i <= N; i ++)
    {
        if (!vis[i]) primes[++ cnt] = i;
        for (int j = 1; i * primes[j] <= N; j ++)
        {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

因数 / 约数

其中 max⁡{ω(n)}\max \{ \omega(n) \} 表示 nn 以内不同质因子的最大个数，max⁡{d(n)}\max \{ d(n) \} 表示 nn 以内最大的约数个数。

O(n)O(\sqrt n) 求出所有约数

1
2
3
4
5
6
7
8
9
10
11
12
13
int divs[N], cnt;

inline void divide(int x)
{
    for (int i = 2; i <= x / i; i ++)
    {
        if (x % i == 0)
        {
            divs[++ cnt] = i;
            if (i != x / i) divs[++ cnt] = x / i;
        }
    }
}

O(n)O(\sqrt n) 求出所有质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int divs[N], cnt;

inline void divide(int x)
{
    int temp = x;    // 不能直接使用 x
    for (int i = 2; i <= x / i; i ++)
    {
        if (temp % i == 0)
        {
            while (temp % i == 0) temp /= i;
            divs[++ cnt] = i;
        }
    }
    if (temp > 1) divs[++ cnt] = temp;
}

通过预处理出范围内的所有质数可以进一步优化至 O(p(n))O(\sqrt{p(n)})，其中 p(n)p(n) 为 nn 范围内的所有质数数量，数量级上限大约为 nln⁡n\frac{n}{\ln n}，大约优化了 ln⁡n\sqrt{\ln n} 的常数时间，约等于没有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int primes[N], tot;
int divs[N], cnt;

inline void divide(int x)
{
    int temp = x;
    for (int i = 1; primes[i] <= x / primes[i]; i ++)
    {
        if (temp % primes[i] == 0)
        {
            while (temp % primes[i] == 0) temp /= primes[i];
            divs[++ cnt] = primes[i];
        }
    }
    if (temp > 1) divs[++ cnt] = temp;
}

欧拉函数

欧拉函数 φ(n)\varphi(n) 表示小于等于 nn 的与 nn 互质的数的个数。特别的，素数的欧拉函数 φ(p)=p−1\varphi(p) = p - 1。

欧拉函数有如下性质：

  1. 是积性函数，∀gcd⁡(a,b)=1\forall \gcd(a, b) = 1，都有 φ(a,b)=φ(a)φ(b)\varphi(a, b) = \varphi(a) \varphi(b)

  2. n=∑d∣nφ(d)n = \sum_{d \mid n} \varphi(d)​

  3. 如果 gcd⁡(a,m)=1\gcd(a, m) = 1，则有 aφ(m)≡1(modm)^{\varphi(m)} \equiv 1 \pmod m

  4. 由容斥原理可知，φ(n)\varphi(n) 可以由公式：

n=∏i=1ω(n)piki,∀pi∈Pφ(n)=n×∏i=1npi−1pin = \prod_{i = 1}^{\omega (n)} p_i^{k_i},\forall p_i \in \mathbb{P} \\ \varphi(n) = n \times \prod_{i = 1}^n \frac{p_i - 1}{p_i}

得到，具体证明由性质 11 得出。

根据性质 44，我们可以在 O(n)O(\sqrt n) 或者 O(nln⁡n)O(\sqrt{\frac{n}{\ln n}}) 的时间复杂度内求出一个数的欧拉函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int divs[N], cnt;

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

欧几里得算法

O(log⁡max⁡(a,b))O(\log \max(a, b)) 求 gcd⁡(a,b)\gcd(a, b)

1
int gcd(int a, int b) { return a == 0 ? b : gcd(b, a % b); }
1
2
3
4
5
int gcd(int a, int b)
{
    if (a == 0) return b;
    else return gcd(b, a % b); 
}

O(log⁡max⁡(a,b))O(\log \max(a, b)) 求线性同余方程

线性同余方程通常指形如 ax≡b(modn)ax \equiv b \pmod n，可以改写为 ax+nk=bax + nk = b，其中 a,n,ba,n,b 已知，求出 x,kx,k。

  • 由裴蜀定理可知，方程有整数解当且仅当 gcd⁡(a,n)∣b\gcd(a, n) \mid b。

  • 由扩欧可知，若得到其中一组解，剩余解都可以直接计算得出。

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}    // 返回值为 gcd(a, b)

具体做法证明暂时忽略。

快速幂

O(n)O(n) 正常做法

1
2
3
for (int i = 1; i <= k; i ++)
    res = res * base % mod;
return res;

O(log⁡n)O(\log n) 位运算快速幂

1
2
3
4
5
6
7
8
9
inline int ksm(int base, int k, const int mod = ::mod)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * base % mod;
        base = base * base % mod, k >>= 1;
    }
}

逆元

扩欧求逆元

所求的显然就是 ax≡1(modb)ax \equiv 1 \pmod b 中的 xx，即 a mod ba \bmod b 的逆元，记为 a−1a^{-1}。

1
2
3
4
5
6
7
void exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
        return x = 1, y = 0, void();
   exgcd(b, a % b, y, x);
   y -= a / b * x;
}

费马小定理求逆元

1
inline int getinv(int x, int mod) { return ksm(x, mod - 2, mod); }

两者的时间复杂度均为 O(log⁡b)O(\log b)。

O(n)O(n) 求阶乘逆元

1
2
3
4
5
6
7
8
9
10
int fc[N], inv[N];

void Init()
{
    for (int i = fc[0] = 1; i < N; i ++)
        fc[i] = fc[i - 1] * i % mod;
    inv[N - 1] = ksm(fc[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i --)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}

O(n)O(n) 预处理连续逆元

如果要求出 ∀i−1≡1(modp),i∈[1,n]\forall i^{-1} \equiv 1 \pmod p,i \in [1, n]，单次查询复杂度要求小于 O(log⁡p)O(\log p) 可以用这一种方法。

首先有 1−1≡1(modp)1^{-1} \equiv 1 \pmod p，然后设 k=⌊pi⌋k = \left \lfloor \frac{p}{i} \right \rfloor，r=p mod ir = p \bmod i，则会有：

k×i+r≡0(modp)k \times i + r \equiv 0 \pmod p

接着乘上 ii 和 rr 的逆元 i−1i^{-1} 和 r−1r^{-1}，可以得到：

k×r−1+i−1≡0(modp)i−1≡−k×r−1(modp)i−1≡−⌊pi⌋×(p mod i)−1(modp)k \times r^{-1} + i^{-1} \equiv 0 \pmod p \\ i^{-1} \equiv -k \times r ^{-1} \pmod p \\ i^{-1} \equiv -\left \lfloor \frac{p}{i} \right \rfloor \times (p \bmod i) ^ {-1} \pmod p

通过线性递推可以直接得出 (p mod i)−1(p \bmod i) ^ {-1}，因此时间复杂度为 O(n)O(n)。

1
2
3
inv[1] = 1;
for (int i = 2; i < N; i ++)
    inv[i] = -(mod - mod / i) * inv[mod % i] % mod;

组合数

组合数的预处理都一样，放在一起算了。

Pn=n!Ank=n!(n−k)!Cnk=(nk)=n!k!(n−k)!P_{n}=n! \\ A_{n}^{k}=\frac{n!}{\left( n-k \left) !\right. \right.} \\ C_{n}^{k} = \binom{n}{k} = \frac{n!}{k!(n - k)!} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inline int ksm(int base, int k, const int mod = ::mod)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * base % mod;
        base = base * base % mod, k >>= 1;
    }
}

int fc[N], inv[N];

inline int A(int n, int m) { return n < m ? 0 : inv[n] * inv[n - m] % mod; }

inline int C(int n, int m) { return n < m ? 0 : inv[n] * inv[n - m] % mod * inv[m] % mod; }

void Init()
{
    for (int i = fc[0] = 1; i < N; i ++)
        fc[i] = fc[i - 1] * i % mod;
    inv[N - 1] = ksm(fc[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i --)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}
1
2
3
4
5
6
7
8
9
10
11
int C[N][N];

void Init()
{
    for (int i = 0; i < N; i ++)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j ++)
            C[i][j] = (C[i - 1][j - 1] + C[i][j - 1]) % mod;
    }
}