数论基础算法模板

a^phi(n)^ ≡ 1 (mod n) 在gcd(a, n) = 1下成立

求组合数

时间复杂度(O(n^2^))

1
2
3
4
5
6
7
8
9
int C[N][N];

void init()
{
    for (int a = 0; a < N; a ++ )
        for (int b = 0; b <= a; b ++ )
            if (!b) C[a][b] = 1;
            else C[a][b] = C[a - 1][b - 1] + C[a - 1][b];
}

时间复杂度(O(nlogn))

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
//首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
//如果取模的数是质数，可以用费马小定理求逆元
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010, MOD = 1e9 + 7;

int n;
LL ft[N], ift[N];

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

int main()
{
    ft[0] = 1, ift[0] = 1;

    for (int i = 1; i < N; i ++ )
    {
        ft[i] = ft[i - 1] * i % MOD;
        ift[i] = qmi(ft[i], MOD - 2, MOD);  //求ft[i]的逆元
    }

    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        //  C[a][b]: a! / b! / (a - b)! => a! * (b!)的乘法逆元 * (a - b)!的乘法逆元
        printf("%d\n", ft[a] * ift[b] % MOD * ift[a - b] % MOD);
    }

    return 0;
}

Lucas定理求组合数(O(plog^p^log^n^))

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
47
48
49
50
51
52
53
54
55
56
57
58
59
//若p是质数，则对于任意整数 1 <= m <= n，有：
//C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


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


int C(int a, int b, int p)
{
    if (b > a) return 0;

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


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


int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

高精度组合数

当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
1. 筛法求出范围内的所有质数
2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + …
3. 用高精度乘法将所有质因子相乘

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>

using namespace std;

const int N = 5010;

int p[N], cnt, num[N]; //num[i]:质数p[i]在Cab中的指数
bool st[N];

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

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;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//获取n!中的因子p的指数
int get(int a, int b)
{
    int res = 0;
    while (a)
    {
        res += a / b;
        a /= b;
    }
    return res;
}

////算术基本定理分解Cab，再乘起来  Cab:a! / b! / (a - b)!
int main()
{
    get_ps(N);

    int a, b;
    cin >> a >> b;

    for (int i = 0; i < cnt; i ++ )
        num[i] = get(a, p[i]) - get(b, p[i]) - get(a - b, p[i]);

    vector<int> res;
    res.push_back(1);
    for (int i = 0; i < cnt; i ++ )
        while (num[i] -- )
            res = mul(res, p[i]);
    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);

    return 0;
}

exgcd

时间复杂度O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

exgcd求解线性同余方程

n组数据ai,bi,mi，对每组数求出一个xi，满足ai * xi ≡ bi (mod mi)，无解输出impossible

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
#include <iostream>

using namespace std;

typedef long long LL;

int n;

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

int main()
{
    cin >> n;
    while (n -- )
    {
        LL a, b, m, x, y;
        scanf("%d%d%d", &a, &b, &m);
        LL gcd = exgcd(a, m, x, y);
        if (b % gcd) puts("impossible");
        else
        {
            x *= b / gcd;
            LL tmp = m / gcd;
            x = (x % tmp + tmp) % tmp;
            printf("%lld\n", x);
        }
    }

    return 0;
}

快速幂求逆元

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
#include <iostream>

using namespace std;

typedef long long LL;

int n;

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

//费马小定理: a ** phi(p) 同余 1 (mod p)     即 a * (a ** (p - 2)) 同余 1 (mod p)
int main()
{
    cin >> n;
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}

欧拉函数

用定义求

1
2
3
4
5
6
7
8
9
10
11
12
13
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
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
int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


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

高斯消元

高斯消元解线性方程组

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;  //double与0比较一定要用eps

double a[N][N];
int n;

//返回值 0:无解 1:唯一解 2:无穷多解
int gauss()
{
    int r, c;
    //枚举每一列
    for (r = 1, c = 1; c <= n; c ++ )
    {
        //找当前列绝对值最大的一行
        int mx = r;
        for (int i = r; i <= n; i ++ )
            if (fabs(a[i][c]) > fabs(a[mx][c]))
                mx = i;

        //绝对值最大的一行a[mx][c]为0，跳过
        if (fabs(a[mx][c]) < eps) continue;

        //换到当前的第一行
        for (int j = c; j <= n + 1; j ++ ) swap(a[r][j], a[mx][j]);

        //a[r][c]化为1
        for (int j = n + 1; j >= c; j -- ) a[r][j] /= a[r][c];

        //更新后面的行
        for (int i = r + 1; i <= n; i ++ )
            for (int j = n + 1; j >= c; j -- )
                a[i][j] -= a[i][c] * a[r][j];

        r ++ ;
    }

    if (r < n + 1)
    {
        //第r列开始应该都为 0 = 0 否则无解
        for (int i = r; i <= n; i ++ )
            if (fabs(a[i][n + 1]) > eps)
                return 0;
        return 2;
    }

    //求出唯一解
    for (int i = n; i >= 1; i -- )
        for (int j = i + 1; j <= n; j ++ )
            a[i][n + 1] -= a[j][n + 1] * a[i][j];
    return 1;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n + 1; j ++ )
            cin >> a[i][j];

    int t = gauss();
    if (t == 0) puts("No solution");
    else if (t == 1)
        for (int i = 1; i <= n; i ++ )
            printf("%.2lf\n", a[i][n + 1]);
    else puts("Infinite group solutions");

    return 0;
}

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

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>

using namespace std;

const int N = 110;

int n, a[N][N];

int gauss()
{
    int r, c;
    for (r = 1, c = 1; c <= n; c ++ )
    {
        int mx = r;
        for (int i = r; i <= n; i ++ )
            if (a[i][c])
                mx = i;

        if (!a[mx][c]) continue;

        for (int j = c; j <= n + 1; j ++ ) swap(a[r][j], a[mx][j]);

        for (int i = r + 1; i <= n; i ++ )
            if (a[i][c])
                for (int j = n + 1; j >= c; j -- )
                    a[i][j] ^= a[r][j];

        r ++ ;
    }

    if (r < n + 1)
    {
        for (int i = r; i <= n; i ++ )
            if (a[i][n + 1])
                return 0;
        return 2;
    }

    for (int i = n; i >= 1; i -- )
        for (int j = i + 1; j <= n; j ++ )
            if (a[i][j])
                a[i][n + 1] ^= a[j][n + 1];
    return 1;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n + 1; j ++ )
            cin >> a[i][j];

    int t = gauss();
    if (t == 0) puts("No solution");
    else if (t == 1)
        for (int i = 1; i <= n; i ++ )
            printf("%d\n", a[i][n + 1]);
    else puts("Multiple sets of solutions");

    return 0;
}

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//a = b * c
typedef long long LL;

void mul(LL a[N][N], LL b[N][N], LL c[N][N])
{
    LL t[N][N] = {0};
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int k = 1; k <= n; k ++ )
                t[i][j] = (t[i][j] + b[i][k] * c[k][j]) % MOD;
    memcpy(a, t, sizeof t);
}

while (k)
{
    if (k & 1) mul(res, res, A);
    mul(A, A, A);
    k >>= 1;
}

扩展中国剩余定理excrt

题目

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
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>

using namespace std;

typedef long long LL;

LL n, m1, a1, m2, a2;
bool error;

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

/*
    x ≡ mi(mod ai)
    x = m1 + a1 * t1,  x = m2 + a2 * t2
    联立得:a1 * t1 + a2 * t2 = m2 - m1
    gcd | (m2 - m1) 有解
    exgcd(a1, a2, t1, t2)解出 a1 * t1 + a2 * t2 = gcd 中的 t1
    t1 = t1 * (m2 - m1) / gcd
    通解t1' = t1 + k * a2 / gcd
    代入得 x = (m1 + a1 * t1) + k * (a1 * a2 / gcd)
    括号1看作新的m1   括号2看作新的a1
    遍历所有方程   最后 x = (m1 % a1 + a1) % a1
*/
int main()
{
    cin >> n >> a1 >> m1;

    while ( -- n)
    {
        cin >> a2 >> m2;
        LL t1, t2;
        LL gcd = exgcd(a1, a2, t1, t2);
        if ((m2 - m1) % gcd)
        {
            error = true;
            break;
        }
        t1 *= (m2 - m1) / gcd;
        LL tmp = a2 / gcd;
        t1 = (t1 % tmp + tmp) % tmp;
        m1 = m1 + a1 * t1;
        a1 *= a2 / gcd;
    }

    if (error) puts("-1");
    else cout << (m1 % a1 + a1) % a1;

    return 0;
}