0%

算法基础（10）

发表于 更新于 分类于 本文字数： 1.2k
第四章数学知识内容：数论（质数，约数）

质数

在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者素数。

1.质数的判定——试除法

暴力做法，1到$n$遍历——时间复杂度$O(n)$

优化：n的约数都是成对出现，因此枚举时只枚举其中较小的一个，即2到$\sqrt{n}$，时间复杂度$O(\sqrt{n})$（推荐写成1 <= n / i，若是i <= sqrt(n)，比较费时间；若是i * i <= n，当n接近int的最大值时，i * i有溢出风险。）

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

2.分解质因数——试除法

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。

给定n个正整数$a_i$，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

暴力做法：从小到大枚举所有数，$O(n)$

优化：n中最多只包含一个大于$\sqrt{n}$的质因数，最坏情况$O(\sqrt{n})$，最好情况$O(\log n)$（如当$n-2^k$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void divide(int n)
{
	for(int i = 2; i <= n / i; i++)
        if(n % i == 0)  // i 一定是质数
        {
        	int s = 0;  //求底数的指数
            while(n % i == 0)
            {
				n /= i;
                s++;
            }
            printf("%d%d\n", i, s);
        }
    if(n > 1)  printf("%d %d\n", n, 1);
    puts("");
}

3.筛质数

给定一个正整数n，请你求出1~n中质数的个数。

朴素做法：将所有数从小到大排列，依次把每个数的倍数删掉，剩下的数就是从2到n的质数。（如果p没有被删掉，说明从2到p-1中不存在任何一个p的约数，那p一定是质数。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int get_primes(int n)
{
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            prime[cnt ++] = i;
        }
        
        for(int j = i + i; j <= n; j += i)  st[j] = true;
    }
    return cnt;
}

时间复杂度：$O(n \log n)$

优化：并不需要把每个数的倍数删掉，只需把每个质数的倍数删掉，代码只需很小的改动。——时间复杂度：$O(n \log \log n)$，很接近$O(n)$了。（1到n中有$n / \ln n$个质数）

埃氏筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
int get_primes(int n)
{
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            prime[cnt ++] = i;
            for(int j = i + i; j <= n; j += i)  st[j] = true;
        }
    }
    return cnt;
}

优化2：线性筛法，也称为欧拉筛法，思路是：n只会被它的最小质因子筛掉。当$n=10^7$时，线性筛法大概比埃氏筛法快一倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int get_primes(int n)   //线性筛法
{
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])   prime[cnt ++] = i;
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0)  break;   //prime[j]一定是i的最小质因数
        }
    }
    return cnt;
}

如果i % prime[j] == 0，prime[j]一定是i的最小质因数，prime[j] 一定是prime[j] * i的最小质因数；如果i % prime[j] != 0，说明prime[j]一定小于i的最小质因数，所以prime[j]也一定是prime[j] * i的最小质因数。

任何一个合数一定会被筛掉，它一定存在一个最小质因数，设为prime[j]，当i枚举到x / prime[j]时，它就会被筛掉。因为我们是用最小质因子来筛数，而每个数只有一个最小质因子，因此时间复杂度是线性的，即$O(n)$。

约数

1.试除法求约数

给定n个正整数$a_i$，对于每个整数$a_i$,请你按照从小到大的顺序输出它的所有约数。

思路和试除法判断质数相似，从小到大枚举n的约数（只枚举一对中小的那个），时间复杂度为$O(\sqrt{n})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> get_divisors(int n)
{
    vector<int> res;
    
    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());
    return res;
}

2.约数个数

定理：如果一个数因数分解之后可以写成：$N=p_1^{ \alpha_1} \cdot p_2^{\alpha_2} \cdot \dots p_k^{\alpha_k}$，那么它的约数个数为：$(\alpha_1+1)(\alpha_2+1)\dots (\alpha_3+1)$。

（数N的约数d一定可以写成：$d=p_1^{ \beta_1} \cdot p_2^{\beta_2} \cdot \dots p_k^{\beta_k}$，其中对每一个$\beta_i$，一定有$0 \le \beta_i \le \alpha_i$；N的每一个约数就对应着一组不同的$\beta_i$的取值，因此N的约数的个数就是$\beta_i$的不同取值的组合数，即$(\alpha_1+1)(\alpha_2+1)\dots (\alpha_3+1)$。）

冷知识：int范围内的整数，约数个数最多的数，它的约数大约有1500个

给定n个正整数$a_i$，请你输出这些数的乘积的约数个数，答案对$10^9+7$取模。

题目是让求数$a_1 \cdot a_2 \dots a_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
#include<iostream>
#include<unordered_map>
using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    
    unordered_map<int, int> primes;
    
    while(n--)
    {
        int x;
        cin >> x;
        
        for(int i = 2; i <= x / i; i++)
            while(x % i == 0)
            {
                x /= i;
                primes[i] ++;
            }
        if(x > 1)  primes[x] ++;
    }
    
    LL res = 1;
    for(auto prime : primes)  res = res * (prime.second + 1) % mod;
    
    cout << res << endl;
    
    return 0;
}

3.约数之和

定理：如果一个数因数分解之后可以写成：$N=p_1^{ \alpha_1} \cdot p_2^{\alpha_2} \cdot \dots p_k^{\alpha_k}$，那么它的约数之和为：$(p_1^{ 0} + p_1^{1}+ \dots p_1^{\alpha_1})(p_2^{ 0} + p_2^{1}+ \dots p_2^{\alpha_2}) \dots (p_k^{ 0} + p_k^{1}+ \dots p_k^{\alpha_k})$。

（将上式展开，一共有$(\alpha_1+1)(\alpha_2+1)\dots (\alpha_3+1)$项，每一项都是$p_1^{ \beta_1} \cdot p_2^{\beta_2} \cdot \dots p_k^{\beta_k}$，都是N的一个约数，且每个数都不同，则上式就是N的约数之和。）

给定n个正整数$a_i$，请你输出这些数的乘积的约数之和，答案对$10^9+7$取模。

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

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    
    unordered_map<int, int> primes;
    
    while(n--)
    {
        int x;
        cin >> x;
        
        for(int i = 2; i <= x / i; i++)
            while(x % i == 0)
            {
                x /= i;
                primes[i] ++;
            }
        if(x > 1)  primes[x] ++;
    }
    
    LL res = 1;
    for(auto prime : primes)   //代码和上题基本一样，只需按求约数和的公式改动一下即可
    {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while(a--)   t = (t * p + 1) % mod;   //这一步可以用分治优化到log a的复杂度，但在这个题中其实没必要
        res = res * t % mod;
    }
    
    cout << res << endl;
    
    return 0;
}

4.求最大公约数

欧几里得算法，也叫辗转相除法。a和b的最大公约数$=$ a模b和b的最大公约数，$(a, b)=(b, a \, mod \,b)$，这样就可以用递归写了，时间复杂度为$O(\log n)$。

（设$a \,mod\, b=a-c \cdot b$，则$(a, b)=(b, a-c \cdot b)$。由d能整除a，d能整除b，则d能整数ax + by，这证上式成立。）

给定n对正整数$a_i,b_i$，请你求出每对数的最大公约数。

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

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;   //a和0的最大公约数是a
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while(n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    
    return 0;
}