数论

质数 Primes

质数的性质

数学符号“∣”的意义,如a∣b： ‘|’为整除符号，对于整数a,b(a≠0),若存在整数k,使b=ka,则称a整除b,或b能被a整除,记为a∣b。

d | n => n / d | n

也就是说 a * b = c, c能整除a, 也能整除b. 我们找质数只要遍历一遍较小的a即可

质数定理

在 1~n中有n / lnn个质数

试除法判定质数

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

const int N = 110;

bool is_Prime(int x)
{
  	// 从质数的性质出发判断质数;
    if(x < 2) return false;
   
    // 等价于 i * i <= x或者i <= sqrt(x)
    for(int i = 2; i <= x / i; i++)
        if(!(x % i)) return false;
    return true;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        if(is_Prime(x)) cout<< "Yes";
        else cout << "No";
        cout << endl;
    }
    return 0;
}

试除法分解质因数

从小到大分别从n中除干净某个数

最后如果n不是1, 则说明最后一个质数大于根号n, 再单独输出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
#include<iostream>
using namespace std;

int divied(int x)
{
    for(int i = 2; i <= x / i; i++)
    {
      	// 判断是否能被整除
        if(x % i == 0)
        {
            int t = 0;
          
          	// 在x中除干净i
            while(x % i == 0)
            {
                x /= i;
                t ++;
            }
          
          	// 输出质数和次数
            cout << i << ' ' << t << endl;
        }
    }
    
  	// 如果最后除不干净,说明还有大于根号n的质数,即是自己本身
    if(x != 1) cout << x << ' ' << 1 << endl;
    return 0;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        divied(x);
        cout << endl;
    }
    return 0;
}

筛质数

我们把所有数的倍数全都删掉,剩下的数中间全部都不是 2 ~ p - 1的倍数

朴素代码 O(nlnn)

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>
using namespace std;
const int N = 10e6 + 10;
int st[N];

int get_primes(int n)
{
    int ret = 0;
  	// 遍历所有数
    for(int i = 2; i <=n; i++)
      
      	// 如果没有被删除, 遍历i+1之后的数
        if(!st[i]) for(int j = i + 1; j <= n; j++)
        {
            if(j % i == 0) {
              	// 删除数字并累计个数
                if(!st[j])
                {
                    st[j] = 1;
                    ret ++;
                }
            }
        }
        
  	// 总数减去被删掉的个数就是剩下的质数
    return n - ret - 1;
}

int main()
{
    int n;
    cin >> n;
    cout << get_primes(n);
    return 0;
}

优化方案, 我们不需要将每个数的倍数全部删掉,只需要把质数的倍数全部删掉. 减少重复计算量.

埃式筛法 O(n loglogn)

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

const int N = 10e6+10;

int prime[N];
int cnt;
char st[N];

int get_prime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(st[i] == 0)
        {
            prime[++cnt] = i;
          	// 每次删除i所有的倍数
        		for(int j = 2 * i; j <= n; j += i) st[j] = 1;
        }
    }
    
    return cnt;
}

int main()
{
    int n;
    cin >> n;
    cout << get_prime(n);
    return 0;
}

线性筛法

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
#include<iostream>
using namespace std;
const int N = 10e6 + 10;
int st[N];
int primes[N];
int cnt;

int get_primes(int n)
{
  	// 从2开始遍历
    for(int i = 2; i <= n; i++)
        {
      			// 如果没有被删掉, 质数存入primes
            if(!st[i]) primes[cnt++] = i;
      
      			// 从第一个质数到当前质数全都遍历一遍, n 只被最小质数删除
            for(int j = 0; primes[j] <= n / i ; j++)
            {
                st[primes[j] * i] = 1;
              
              	// i % primes[j] == 0 情况下 primes[j] 一定是i的最小质因子,
                // 同样也是primes[j] * i的最小质因子
              	// i % primes[j] != 0 一定小于i的所有质因子也是primes[j] * i的最小质因子
              	// 对于一个合数x, 假设pj是x的最小质因子, 当i枚举到 x / pj 的时候, x一定会被删去, 且每一个合数只会被删除一次, 所以是线性的
                if(primes[j] % i == 0) break;
            }
        }
        
    return cnt;
}

int main()
{
    int n;
    cin >> n;
    cout << get_primes(n);
    return 0;
}

当 $ n >= 10^{7}$ 时 线性筛法比埃式筛法快1倍

约数

int范围内的整数, 约数最多的个数为1500

试除法求约数 $O(\sqrt{n})$

遍历$ [1 , \sqrt{n}]$中所有的数,

如果能被$n$整除添加到答案中

特判$ n = i * i $的情况

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

const int N = 110;

vector<int> get_divisors(int n)
{
    vector<int> ret;
    for(int i = 1; i <= n / i; i++)
    {
        if(n % i == 0) 
        {
            ret.push_back(i);
            if(i != n / i) ret.push_back(n / i);
        }
    }
    sort(ret.begin(),ret.end());
    
    return ret;
}

int main()
{
    int m;
    cin >> m;
    while(m--)
    {
        int n;
    cin >> n;
    vector<int> ret = get_divisors(n);
    for(auto &p : ret) cout << p << ' ';
    cout << endl;
    }
    
    return 0;
    
}

约数个数和约数之和

数学原理: 质因子分解

image-20230218173404409

约数个数
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<iostream>
#include<unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> prime;
    while(n--)
    {
        int x;
        cin >> x;
        
        // 分解质因数
        for(int i = 2; i <= x / i; i++)
        {
            while(x % i == 0)
            {
                x /= i;
                prime[i]++;
            }
        }
        
      	// 大于根号x的质因数是否存在
        if(x > 1) prime[x]++;
    }
    
    long long ret = 1;
    for(auto &p:prime) ret = ret * (p.second + 1) % mod;
    
    cout << ret;
    
    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
#include<iostream>
#include<unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> prime;
    while(n--)
    {
        int x;
        cin >> x;
        
        // 分解质因数
        for(int i = 2; i <= x / i; i++)
        {
            while(x % i == 0)
            {
                x /= i;
                prime[i]++;
            }
        }
        
        if(x > 1) prime[x]++;
    }
    
    long long ret = 1;
    for(auto &p:prime) 
    {
        int a = p.first, b = p.second;
        long long t = 1;
        
        // 秦九昭算法
        while(b--)
        {
            t = (t * a + 1) % mod;
        }
        
        ret = ret * t % mod;
    }
    
    cout << ret;
    
    return 0;
}

秦九昭算法 计算多项式之和

最大公约数 (欧几里得算法,辗转相除法)

算法原理

$d | a$ $d|b$ $d| ax + by$

$\gcd(a.b) = \gcd(b,a\mod b)$

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

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



int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x, y;
        cin >> x >> y;
        cout << gcd(x,y) << endl;
    }
    
    return 0;
}