数论-1

质数

定义：针对大于一的整数，如果只包含 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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 5;

int num[N];

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        memset(num, 0, sizeof(num));
        for (int i = 2; i <= n / i; i ++ )
        {
            //  每一个合数都可以用比它小的质数表示
            int s = 0;
            while(n % i == 0)   //  所以第一次找到的一定是一个质数
            {
                n /= i;
                s ++ ;
            }
            if (s) printf("%d %d\n", i, s); // i一定是质数，s为其出现的次数
        }
        if (n > 1) printf("%d 1\n", n);
        // 优化利用性质：n中最多只有一个大于sqrt(n)的质因子
        // 如果还有数那么一定只有这一个未被除过的，直接输出就好
        printf("\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
#include <iostream>

using namespace std;

const int N = 1e6 + 5;

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

int main()
{
    int n;
    cin >> 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;  // prime[j]一定是i的最小质因子
        }
    }
    printf("%d", cnt);
    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
#pragma GCC diagnostic error "-std=c++11"
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#define debug(x) cout << #x << " = " << x << endl;

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e6 + 5, mod = 1e9 + 7;
const double esp = 1e-6;

int main()
{
    int t;
    cin >> t;
    vector<int> res;
    while (t--) {
        int n;
        cin >> n;
        res.clear();
        for (int i = 1; i <= n / i; i ++ )
        {
            if (n % i == 0)
            {
                res.push_back(i);
                if(i != n / i)  res.push_back(n / i);
            }
        }
        sort(res.begin(), res.end()); //  排序保证输出的是有序的
        for (auto x:res)
        {
            printf("%d ", x);
        }
        printf("\n");
    }
    return 0;
}

约数个数

如果 p 为质数

则约数个数为 本质上是利用了乘法原理

其中所有约数对应了任一个质数可以选择 次的幂的情况

int 范围内约数个数最多的大约有 1500 个

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
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>

#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e6 + 5, mod = 1e9 + 7;
//const double esp = 1e-6;

int main()
{
    int t;
    cin >> t;
    map<int, int> primes;
    while (t--) {
        int n;
        cin >> n;
        for(int i = 2; i <= n / i; i ++ )
        {
            while (n % i == 0)
            {
                n /= i;
                primes[i] ++ ;
            }
        }
        if(n > 1) primes[n] ++ ;
    }
    LL res = 1;
    for (auto prime : primes)  res = res * (prime.second + 1) % mod;
    printf("%lld\n", res);
    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
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e6 + 5, mod = 1e9 + 7;
//const double esp = 1e-6;
map<int, int> primes;
int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int n;
        cin >> n;
        for (int i = 2; i <= n / i; i ++)
        {
            while (n % i == 0)
            {
                primes[i] ++ ;
                n /= i;
            }
        }
        if (n > 1)  primes[n] ++ ;
    }
    LL res = 1;
    for (auto p : primes)  // 按照求和的公式进行计算
    {
        LL a = p.first, b = p.second;
        //  a是底数，b是指数
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        //  利用秦九韶算法, 每次乘以加一---复杂度O(n)
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

最大公约数

欧几里得算法(辗转相除法)

时间复杂度：

核心原理：

1
2
3
4
int gcd(int a, int b)
{
 return b ? gcd(b, a % b) : 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
36
37
38
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

//const int N = 1e6 + 5, mod = 1e9 + 7;
//const double esp = 1e-6;

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

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int a;
        cin >> a;
        printf("%d\n", Eular(a));
    }
    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
#pragma GCC diagnostic error "-std=c++11"
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e6 + 5, mod = 1e9 + 7;

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

void get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            phi[i] = i - 1;  //  i是质数
        }
        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);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_eulers(n);
    LL res = 0;
    for (int i = 1; i <= n; i ++ )
        res += phi[i];
    cout << res << endl;
    return 0;
}

快速幂

模板

求

优化原理：将指数用二进制预处理

复杂度

1
2
3
4
5
6
7
8
9
10
11
LL q_pow(LL a, LL k, LL mod)
{
    LL res = 1;
    while (k)
    {
        if (k&1)  res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

快速幂求乘法逆元

乘法逆元的定义

若整数 ，互质，并且对于任意的整数 ，如果满足 ，则存在一个整数 ，使得，则称 为 的模 乘法逆元，记为 > 存在乘法逆元的充要条件是 与模数 互质。当模数 为质数时， 即为 的乘法逆元

那么等价于求

用快速幂q_pow(b, m - 2, m)即可

注意：当 时无解

扩展欧几里得算法

裴蜀定理

对于任意正整数，一定存在非零整数，使得

请求出一组 满足 

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

解线性同余方程组

求出一个满足上式的

上式等价于

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
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

//const int N = 1e6 + 5, mod = 1e9 + 7;
//const double esp = 1e-6;

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 t;
    cin >> t;
    while (t--)
    {
        int a, b, m, x, y;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);
        if(b % d) printf("impossible\n");
        else
        {
            x = (LL)x * b / d % m;
            cout << x << endl;
        }
    }
    return 0;
}

求逆元

逆元为满足

等价于$a x + k p = 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
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

//const int N = 1e6 + 5, mod = 1e9 + 7;
//const double esp = 1e-6;

LL exgcd(LL a, LL b, LL &x, LL &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()
{
    LL t;
    cin >> t;
    while (t--)
    {
        LL a, p, x, y;
        cin >> a >> p;
        LL d = exgcd(a, p, x, y);
        if(d != 1) printf("impossible\n");
        else
        {
            cout << (x + p) % p << endl; // 防止出现负数
        }
    }
    return 0;
}

线性求逆元

通过递推式来求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

const int N = 3e6 + 5;

typedef long long LL;
LL inv[N];

int main()
{
    LL n, mod;
    cin >> n >> mod;
    inv[1] = 1;
    for (int i = 2; i <= n; i ++ )
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= n; i ++ )
        printf("%ld\n", inv[i]);
    return 0;
}