AcWing 第4讲 数学知识

试除法判断质数

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
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;

        bool flag = true;
        if (a == 1) {
            cout << "No\n";
            continue;
        }
        for (int i = 2;i <= a / i;i++) {
            if (a % i == 0) {
                flag = false;
                cout << "No\n";
                break;
            }
        }
        if (flag)
            cout << "Yes\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
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

void divid(int x) {
    for (int i = 2;i <= x / i;i++) {
        int cnt = 0;
        while (x % i == 0) {
            cnt++;
            x /= i;
        }
        if (cnt) {
            cout << i << " " << cnt << endl;
        }
    }
    if (x > 1) {
        cout << x << " 1\n";
    }
    cout << "\n";
}


int main() {
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        divid(a);
    }
}

质数线性筛法

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
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e6 + 100;
bool st[N];
int cnt, primer[N], top;


int liner(int n) {
    for (int i = 2;i <= n;i++) {
        if (!st[i]) primer[top++] = i;
        for (int j = 0;primer[j] <= n / i;j++) {
            st[primer[j] * i] = true;
            // 用最小质因子更新
            // 若 primer[j] 是i的一个因数，则 primer[j+1]*i 的最小质因数为
            // periemr[j]，会重复筛选
            // 换句话说：i 是 primer[j] 的倍数，那么 primer[j+1] * i 也是
            // primer[j] 的倍数，这个数可以被 primer[j] 筛掉
            if (i % primer[j] == 0) break;
        }
    }
    return top;
}

int main() {
    int n;
    cin >> n;
    cout<<liner(n);


    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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

void divid(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());
    for (int c : res) {
        cout << c << " ";
    }
}

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

    int a;
    while (n--) {
        cin >> a;
        divid(a);
        puts("");
    }
}

约数个数

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;

typedef long long int LL;
const int mod = 1e9 + 7;

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

    LL num = 1;
    unordered_map<int, int> primes;
    
    while (n--) {
        int a;
        cin >> a;
        for (int i = 2; i <= a / i;i++) {
            while (a % i == 0) {
                a /= i;
                primes[i]++;
            }
        }
        if (a > 1) primes[a]++;
    }


    LL ans = 1;
    for (auto ix : primes) {
        ans = ans * (ix.second + 1) % mod;
    }
    cout << ans;
    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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;

typedef long long int LL;
const int mod = 1e9 + 7;



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

    LL num = 1;
    unordered_map<int, int> primes;

    while (n--) {
        int a;
        cin >> a;
        for (int i = 2; i <= a / i;i++) {
            while (a % i == 0) {
                a /= i;
                primes[i]++;
            }
        }
        if (a > 1) primes[a]++;
    }


    LL ans = 1;
    for (auto ix : primes) {
        int a = ix.first, b = ix.second;
        // cout<<a<<" "<<b<<endl;
        int res = 1;
        while (b--)
            res = (res * a + 1) % mod;
        ans *= res;
    }
    cout << ans;
    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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }


    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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;


const int N = 1000010;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        int ans = a;
        for (int i = 2;i <= a / i;i++)
            if (a % i == 0) {
                ans = ans / i * (i - 1);
                while (a % i == 0) a /= i;
            }
        if (a > 1)
            ans = ans / a * (a - 1);
        cout << ans << "\n";
    }


    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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 1001000;
bool st[N];
int primes[N], top = 0;
int phi[N];
LL euler(int n) {
    phi[1] = 1;
    for (int i = 2;i <= n;i++) {
        if (!st[i]) {
            primes[top++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0;primes[j] <= n / i;j++) {
            int t = i * primes[j];
            st[t] = true;
            if (i % primes[j] == 0) {
                phi[t] = phi[i] * primes[j];
                break;
            }
            phi[t] = phi[i] * (primes[j]-1);
        }
    }
    LL sum = 0;
    for (int i = 1;i <= n;i++) sum += phi[i];//, cout << phi[i] << " ";
    return sum;
}

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

    cout<< euler(n);


    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
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;

const int N = 1000010;

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

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, k, p;
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }


    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
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;

const int N = 1000010;

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

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, p;
        cin >> a >> p;
        LL ans = qmi(a, p-2, p);
        if (a % p) cout << ans << endl;
        else cout << "impossible\n";
    }


    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
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;

const int N = 1000010;

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

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        cin >> a >> b;
        int x, y;
        exgcd(a, b, x, y);
        cout << x << " " << y << endl;
    }


    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
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;

const int N = 1000010;

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

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b, m;
        cin >> a >> b >> m;
        int x, y;
        int d = exgcd(a, m, x, y);
        if (b % d == 0)
            cout << (LL)b / d * x % m << endl;
        else
            cout << "impossible\n";
    }


    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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;

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

LL mod(LL a, LL b) {
    return ((a % b) + b) % b;
}

int main() {
    LL n, a1, m1, ans = 0;
    cin >> n >> a1 >> m1;

    for (int i = 0;i < n - 1;i++) {
        LL a2, m2, k1, k2;
        cin >> a2 >> m2;
        LL d = exgcd(a1, a2, k1, k2);
        if ((m1 - m2) % d) {
            // cout<<a1<<" "<<m1<<" "<<a2<<endl;
            ans = -1;
            break;
        }
        k1 *= (m2 - m1) / d;
        // 不能换顺序
        k1 = mod(k1, abs(a2 / d));
        m1 += k1 * a1;
        a1 = abs(a1 / d * a2);
    }

    if (ans != -1)
        ans = mod(m1, a1);
    cout << ans;

    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
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;

const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];

void PRINT() {
    puts("");
    for (int i = 0;i < n;i++) {
        for (int j = 0;j <= n; j++)
            printf("%.2f ", a[i][j]);
        puts("");
    }
}

int guess() {
    // c列，r行

    int c = 0, r = 0;
    for (;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) continue;

        for (int i = 0;i <= n;i++) swap(a[t][i], a[r][i]);
        // 可优化
        for (int i = n;~i;i--) a[r][i] /= a[r][c];

        for (int i = r + 1;i < n;i++) {
            for (int j = n;j >= c; j--) {
                a[i][j] -= a[i][c] * a[r][j];
            }
        }
        r++;
    }
    if (r < n) {
        for (int i = r;i < n;i++)
            if (abs(a[i][n]) > eps)
                return 2;
        return 1;
    }

    for (int i = n - 1;~i;i--)
        for (int j = i + 1;j < n;j++)
            a[i][n] -= a[i][j] * a[j][n];

    return 0;
}

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

    int res = guess();

    if (res == 2) cout << "No solution";
    else if (res == 1)cout << "Infinite group solutions";
    else {
        for (int i = 0;i < n;i++)
            printf("%.2f\n", a[i][n]);
    }
    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
62
63
64
65
66
67
68
69
70
71
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;

const int N = 110;
int n;
int a[N][N];

void PRINT() {
    puts("");
    for (int i = 0;i < n;i++) {
        for (int j = 0;j <= n; j++)
            printf("%d ", a[i][j]);
        puts("");
    }
}

int guess() {
    // c列，r行
    int c = 0, r = 0;
    for (;c < n;c++) {
        int t = r;
        for (int i = r;i < n;i++)
            if (a[i][c]) {
                t = i;
                break;
            }
        if (!a[t][c]) continue;

        for (int i = 0;i <= n;i++) swap(a[t][i], a[r][i]);

        for (int i = r + 1;i < n;i++) {
            if (a[i][c])
                for (int j = n;j >= c; 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;i--)
        for (int j = i + 1;j < n;j++)
            a[i][n] ^= a[i][j] * a[j][n];
    return 0;
}

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

    int res = guess();

    if (res == 2) cout << "No solution";
    else if (res == 1)cout << "Multiple sets of solutions";
    else {
        for (int i = 0;i < n;i++)
            printf("%d\n", a[i][n]);
    }
    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
// 递推公式
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
const int mod = 1e9 + 7;
int ans[2100][2100];
int n;

int main() {
    int a, b;
    for (int i = 0;i < 2000;i++)
        for (int j = 0;j < i;j++) {
            if (!j) ans[i][j] = 1;
            else ans[i][j] = ans[i - 1][j - 1] + ans[i][j - 1];
        }

    cin >> n;
    while (n--) {
        cin >> a >> b;
        cout << ans[a][b] << endl;
    }

    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
// 逆元
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
const int mod = 1e9 + 7;
int n;

int qmi(int a, int b, int c) {
    int ans = 1;
    while (b) {
        if (b & 1)ans = (LL)ans * a % c;
        a = (LL)a * a % c;
        b >>= 1;
    }
    return ans;
}

int main() {
    cin >> n;
    int fact[N] = { 1 }, infact[N] = { 1 };
    for (int i = 1;i < N;i++) {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }

    while (n--) {
        int a, b;
        cin >> a >> b;
        cout << (LL)fact[a] * infact[b] % mod * infact[a - b] % mod << endl;
    }


    return 0;
}

Lucas求组合数

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
// Lucas定理
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;

LL qmi(LL a, LL b, LL c) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % c;
        b >>= 1;
        a = a * a % c;
    }
    return ans;
}

LL C(LL a, LL b, LL c) {
    if (a < b) return 0;
    LL ans = 1;
    for (int i = b + 1, j = 1;j <= a - b;j++, i++) {
        ans = ans * i % c;
        ans = (LL)ans * qmi(j, c - 2, c) % c;
    }
    return ans;
}

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

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


    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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// a,b=input().split(" ");
// a=int(a); b=int(b)
// ans=1
// for j in range(b+1, a+1):
//     ans*=j
// for j in range(1, a-b+1):
//     ans=ans//j
// print(ans)

// 阶乘分解为素数，高精度

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;

const int N = 10100;
bool st[N];
LL primes[N], sum[N];
int cnt;

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

LL get(LL num, LL a) {
    LL ans = 0;
    while (a) {
        ans += a / num;
        a /= num;
    }
    return ans;
}

vector<LL> mul(vector<LL> a, LL num) {
    LL t = 0;
    vector<LL> ret;
    for (int i = 0;i < a.size();i++) {
        t += a[i] * num;
        ret.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        ret.push_back(t % 10);
        t /= 10;
    }
    return ret;
}

int main() {
    LL a, b;
    cin >> a >> b;
    get_primes(a);

    for (int i = 0;i < cnt;i++) {
        LL num = primes[i];
        sum[i] = get(num, a) - get(num, b) - get(num, a - b);
    }

    vector<LL> 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--) {
        cout << res[i];
    }

    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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
const int mod = 1e9 + 7;

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

int main() {
    int n;
    cin >> n;
    int a = 2 * n, b = n;

    LL ans = 1;
    for (int i = b + 1;i <= a;i++)
        ans = ans * i % mod;

    for (int i = 2;i <= a - b;i++)
        ans = ans * qmi(i, mod - 2, mod) % mod;

    ans = ans * qmi(n + 1, mod - 2, mod) % mod;
    cout << ans << endl;

    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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;

int main() {
    int n, m, p[N], ans = 0;
    cin >> n >> m;
    for (int i = 0;i < m;i++) cin >> p[i];

    for (int i = 1;i < 1 << m;i++) {
        int t = 1, s = 0;
        for (int j = 0;j < m;j++) {
            if (i >> j & 1) {
                if ((LL)t * p[j] > n) {
                    t = -1;
                    break;
                }
                t *= p[j];
                s++;
            }
        }
        if (t == -1)continue;

        if (s & 1) ans += n / t;
        else ans -= n / t;
    }
    cout << ans;


    return 0;
}

Nim游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
// 算法竞赛进阶指南 P179
int main() {
    int n, res = 0;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        res ^= a;
    }
    if (res) puts("Yes");
    else puts("No");


    return 0;
}

Nim游戏-台阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;

int main() {
    int n, res = 0;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        int a;
        cin >> a;
        if (i & 1) res ^= a;
    }
    if (res) puts("Yes");
    else puts("No");


    return 0;
}

1
2


#AcWing #算法题 #数论
AcWing 第4讲 数学知识
https://asxjdb.github.io/2023/07/02/AcWing-ch4/
作者
Asxjdb
发布于
2023年7月2日
许可协议