模板-数论

发表于 更新于 分类于

扩展欧几里得算法

(a mod b)x+by=(a−[ab]×b)x+by=ax+b(y−[ab]×x) (a \ mod \ b)x + by \\ = (a - [\frac{a}{b}] \times b)x+by \\ = ax + b(y-[\frac{a}{b}]\times x) 

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

线性同余方程

a×x≡b (mod m)a\times x \equiv b \ (mod \ m)
即
∃y, ax−my=b\exists y,\ ax-my=b

1
2
3
4
5
6
7
8
int solve(int a, int b, int m)
{
    int x, y;
    int d = exgcd(a, m, x, y);
    if (b % d != 0)
        return -1;
    return b / d * x;
}

筛法

朴素筛法 O(nlogn)O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool st[N];
int p[N];
int sieve(int n)
{
    memset(st, 1, sizeof(st))
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            p[cnt++] = i;
        for (int j = 2 * i; j <= n; j += i)
            st[j] = false;
    }
    return cnt;
}
埃氏筛 O(nloglogn)O(nloglogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool st[N];
int p[N];
int sieve(int n)
{
    memset(st, 1, sizeof(st))
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if(st[i])
        {
            p[cnt++] = i;
            for (int j = 2 * i; j <= n; j += i)
                st[j] = false;
        }
    }
    return cnt;
}
欧式筛 O(n)O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int st[N];
int primes[N], idx = 0;
void sieve(int n = N - 5)
{
    memset(st, 1, sizeof(st));
    st[1] = st[0] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            primes[idx++] = i;
        for (int j = 0; i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
int quick_pow(int x, int n)
{
    int timer = x, res = 1;
    while (n != 0)
    {
        if (n & 1)
            res *= timer;
        timer *= timer;
        n >>= 1;
    }
    return res;
}

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int N; // 矩阵维数
using matrix  = array<array<int, N>, N>;

matrix mul(matrix a, matrix b)
{
    matrix ans;
    for (int i = 0; i < N; i++)
    	for (int j = 0; j < N; j++)
    	{
            ans[i][j] = 0;
            for (int k = 0; k < N; k++)
            {
            	ans[i][j] += (a[i][k] * b[k][j]);	
    	    	ans[i][j] %= m;
    	    }
    	}
    return ans;
}

matrix quick_pow(matrix x, int n)
{
    matrix timer = x, res;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (i == j)
                res[i][j] = 1;
            else
                res[i][j] = 0;
    while(n != 0)
    {
    	if (n & 1)
    	    res = mul(res, timer);
    	timer = mul(timer, timer);	
    	n >>= 1;
    }
    return res;
}

阶乘分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int st[N];
int primes[N], idx = 0;
void sieve(int n = N - 5)
{
    memset(st, 1, sizeof(st));
    st[1] = st[0] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            primes[idx++] = i;
        for (int j = 0; i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = false;
            if (i % primes[j] == 0)
                break;
        }
    }
}

int c[N];
for (int i = 0; i < idx; i++)
{
    int s = n, p = primes[i];
    while (s)
    {
        c[i] += s / p;
        s /= p;
    }
}

组合数

1
2
3
4
5
6
7
8
9
10
const int N, MOD;
int c[N][N];
int get_cab(int a, int b)
{
    if (c[a][b] != -1)
        return c[a][b];
    if (b == 0 || a == b)
        return c[a][b] = 1;
    return c[a][b] = (get_cab(a - 1, b) + get_cab(a - 1, b - 1)) % MOD;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using ll = long long;
const int N, MOD;
int fact[N];
int infact[N];
void init()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (ll)fact[i - 1] * i % MOD;
        infact[i] = (ll)
    }
}
int get_cab(int a,int b)
{

}

高斯消元法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int N;
const double eps = 1e-6;
int n;
double a[N][N];

int gauss()
{
    int c, r;
    for (c = 0, r = 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) // 如果最大值是0， 忽略这一行
            continue;

        for (int i = c; i < n + 1; i++) //  把这一行换到最上面
            swap(a[t][i], a[r][i]);

        for (int i = n; i >= c; i--) //将第一个数变成1
            a[r][i] /= a[r][c];

        for (int i = r + 1; i < n; i++) //将下面所有行的第c列清零
            if (fabs(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 = r; i < n; i++)
            if (fabs(a[i][n]) > eps)
                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; //唯一解
}