当前位置:   article > 正文

[AcWing],数学知识(一)质数与约数_质数和约数

质数和约数

在这里插入图片描述

https://www.acwing.com/activity/content/punch_the_clock/11/

质数

质数,在大于1的整数中,有且只有1和他本身两个因数的数,也叫做素数

试除法判定质数

三种写法 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n))

  1. s q r t ( x ) sqrt(x) sqrt(x),函数计算的时间比较高
bool is_prime(int x) {
    // 质数大于1
    if(x < 2) return false;
    for(int i = 2; i <= sqrt(x); i++) {
        if(x % i == 0) return false;
    }
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  1. i × i ≤ x i\times i\leq x i×ix
bool is_prime(int x) {
    // 质数大于1
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

可能会出现TLE情况
在这里插入图片描述
3. i ≤ n / i i \leq n / i in/i

i ≤ x i\leq\sqrt{x} ix
⇒ i 2 ≤ x \Rightarrow i^2\leq x i2x
⇒ i ≤ x i \Rightarrow i\leq\frac{x}{i} iix

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

分解质因数

在这里插入图片描述

时间复杂度 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n))
最坏情况: n = 2 k n = 2^k n=2k,此时时间复杂度为: O ( l o g 2 n ) O(log_2n) O(log2n)
最快情况:时间复杂度为: O ( n ) O(\sqrt{n}) O(n )

做法就是,从 i = 2 i = 2 i=2开始,如果当前数存在 i i i这个因子,那么就记录当前数中存在多少个 i i i的因子,最后整除掉。

可以证明, n n n中最多包含 1 1 1个大于 s q r t ( n ) sqrt(n) sqrt(n)的质因子 x x x
如果有两个,那么 x × x > n x\times x>n x×x>n,所以说最多含有一个大于 s q r t ( n ) sqrt(n) sqrt(n)的质因子,那就是最后无法整除的一个质因数

如果对于一个数 p p p而言,当for循环遍历到 i = p i=p i=p时,就说明 p p p 2 → p − 1 2\rightarrow p-1 2p1中,没有一个因子,所以说 p p p是一个质数

void divide(int x) {
    
    for(int i = 2; i <= x / i; i ++) {
        if(x % i == 0) {
            int cnt = 0;
            while(x % i == 0) {
                cnt ++;
                x /= i;
            }
            printf("%d %d\n",i,cnt);
        }
    }
    
    if(x > 1) printf("%d 1\n",x);
    puts("");
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

筛质数

在这里插入图片描述

时间复杂度 O ( n log ⁡ n ) O(n \log n) O(nlogn)

n 2 + n 3 + . . . + n n \frac{n}{2} + \frac{n}{3}+... + \frac{n}{n} 2n+3n+...+nn
⇒ \Rightarrow n × ( 1 2 + 1 3 + . . . + 1 n ) n\times (\frac{1}{2} + \frac{1}{3}+... + \frac{1}{n}) n×(21+31+...+n1)(调和级数)
⇒ \Rightarrow n × ( ln ⁡ n + C ) n \times (\ln n + C) n×(lnn+C)
⇒ \Rightarrow n × ln ⁡ n n \times \ln n n×lnn
⇒ \Rightarrow n × log ⁡ e n n \times \log_e n n×logen < n × log ⁡ 2 n < n \times \log_2 n <n×log2n

void get_prime() {
    int cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(f[i] == 0) 
            cnt ++;
        // 标记 i 的倍数
        for(int j = i; j <= n; j += i)
            f[j] = 1;
    }
    
    printf("%d\n",cnt);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

但实际上,对于不是质数的数,我们没有必要进入循环判断,所以可以优化一下

这样的时间复杂度为 O ( n log ⁡ log ⁡ n ) O(n \log\log n) O(nloglogn)(埃拉托斯特尼筛法)
用质数就把所有的合数都筛掉

1 → n 1\rightarrow n 1n n l n n \frac{n}{ln n} lnnn个质数,时间复杂度近似为 O ( n log ⁡ log ⁡ n ) O(n \log\log n) O(nloglogn)

什么概念呢,当 n = 2 32 n=2 ^ {32} n=232时, O ( n log ⁡ log ⁡ n ) = 5 O(n \log\log n) = 5 O(nloglogn)=5

void get_prime() {
    int cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(f[i]) continue;
        cnt ++;
        // 标记 i 的倍数
        for(int j = i; j <= n; j += i)
            f[j] = 1;
    }
    
    printf("%d\n",cnt);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

线性筛选

n n n只会被自己的最小质因子筛选掉

  1. i % prime[j] == 0 p r i m e [ j ] prime[j] prime[j]定为 i i i最小质因子, p r i m e [ j ] prime[j] prime[j]也定为 p r i m e [ j ] × i prime[j] \times i prime[j]×i最小质因子
  2. i % prime[j] != 0 p r i m e [ j ] prime[j] prime[j]定小于 i i i的所有质因子,所以 p r i m e [ j ] prime[j] prime[j]也为 p r i m e [ j ] × i prime[j] \times i prime[j]×i最小质因子

每一次向前标记的过程中,都是只遍历到自己的第一个质因子为止,因为标记的过程是在判断之前,所以保证了一定使用了最小质因子对下一个合数进行了标记。

极大减少了重复标记的次数

比如说在埃氏筛选中, 6 6 6会被 2 和 3进行标记,这就发生了重复标记。
而线性筛选就避免了这一情况

在这里插入图片描述

void get_prime() {
    int cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(!f[i]) prime[cnt ++] = i;
        // 线性筛选,枚举所有的质数
        for(int j = 0; prime[j] <= n / i; j++) {
            f[prime[j] * i] = 1;
            if(i % prime[j] == 0) 	//prime[j]一定是i的最小质因子
            	break; 
        }
    }
    
    printf("%d\n",cnt);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

在这里插入图片描述

n = 1 0 7 n=10^7 n=107时,线性筛选法大概会比埃氏筛选法快一倍

约数

试除法求约数

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void get_divisors(int x) {
    vector<int> f;
    for(int i = 1; i <= x / i; i++)
        if(x % i == 0) {
            f.push_back(i);
            if(i != x / i) f.push_back(x / i);
        }
    sort(f.begin(),f.end());
    
    for(auto& e : f) {
        cout << e << " ";
    }
    puts("");
}

int main() {
    int n, x;
    cin >> n;
    
    while (n --) {
        cin >> x;
        get_divisors(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

约数的个数

在这里插入图片描述
对于每一个数 N N N,都可以分解为 N = p 1 α 1 × p 2 α 2 × ⋯ × p k α k N=p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k} N=p1α1×p2α2××pkαk
其中, p 1 p 2 ⋯ p k p_1 p_2 \cdots p_k p1p2pk为质数, α 1 α 2 ⋯ α k \alpha_1 \alpha_2 \cdots \alpha_k α1α2αk为对应的质数的出现次数

所以说,最终的结果可以表示为 a n s = ( α 1 + 1 ) × ( α 2 + 1 ) × ⋯ × ( α k + 1 ) ans=(\alpha_1 + 1) \times (\alpha_2 + 1) \times \cdots \times (\alpha_k+ 1) ans=(α1+1)×(α2+1)××(αk+1)

为什么要 + 1 +1 +1,因为对于每一项 p p p,他对于最终的数 n n n的贡献度来说,一共贡献了 α + 1 \alpha + 1 α+1次,包括他出现的 α \alpha α次与不出现的 1 1 1

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

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

int n;

int main() {
    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) {
                primes[i] ++;
                x /= i;
            }
        if(x != 1) primes[x] ++;
    }
    
    LL res = 1;
    for(auto& e : primes) 
        res = (res * (e.second + 1) ) % mod;
        
    cout << res << 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

约数之和

同理,对于每一个数 N N N,都可以分解为 N = p 1 α 1 × p 2 α 2 × ⋯ × p k α k N=p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k} N=p1α1×p2α2××pkαk,他的约数的个数可以分解为 a n s = ( α 1 + 1 ) × ( α 2 + 1 ) × ⋯ × ( α k + 1 ) ans=(\alpha_1 + 1) \times (\alpha_2 + 1) \times \cdots \times (\alpha_k + 1) ans=(α1+1)×(α2+1)××(αk+1)

那么约数之和,可以分解为: ( p 1 0 + p 1 1 + p 1 2 + ⋯ + p 1 α 1 ) × ( p 2 0 + p 2 1 + p 2 2 + ⋯ + p 2 α 2 ) × ⋯ × ( p k 0 + p k 1 + p k 2 + ⋯ + p k α k ) (p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{\alpha_1}) \times (p_2^0 +p_2^1 + p_2^2 + \cdots + p_2^{\alpha_2}) \times \cdots \times (p_k^0 +p_k^1 + p_k^2 + \cdots + p_k^{\alpha_k}) (p10+p11+p12++p1α1)×(p20+p21+p22++p2α2)××(pk0+pk1+pk2++pkαk)

对于求约数之和,我们可以使用秦九昭算法来做:

对于约数: p k 0 + p k 1 + p k 2 + ⋯ + p k α k p_k^0 +p_k^1 + p_k^2 + \cdots + p_k^{\alpha_k} pk0+pk1+pk2++pkαk
可以化简为: 1 + p k × ( 1 + p k 1 + p k 2 + ⋯ + p k k − 1 ) 1+ p_k \times (1 + p_k^1 + p_k^2 + \cdots +p_k^{k-1}) 1+pk×(1+pk1+pk2++pkk1)
⇒ 1 + p k × ( 1 + p k × ( 1 + p k 1 + p k 2 + ⋯ + p k k − 2 ) ) \Rightarrow 1 + p_k \times (1 + p_k \times (1 + p_k^1 + p_k^2 + \cdots +p_k^{k-2})) 1+pk×(1+pk×(1+pk1+pk2++pkk2))
⇒ 1 + p k × ( ⋯ × ( 1 + p k × ( 1 + p k ) ) ⋯   ) \Rightarrow 1 + p_k \times( \cdots \times (1 + p_k \times (1 + p_k))\cdots) 1+pk×(×(1+pk×(1+pk)))

其中,一共累乘的 p k p_k pk的数量为 k k k

#include <iostream>
#include <algorithm>
#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) {
                primes[i] ++;
                x /= i;
            }
        if(x != 1) primes[x] ++;
    }
    
    LL res = 1;
    for(auto& e : primes) {
        int cnt = e.second, p = e.first;
        LL t = 1;
        while ( cnt -- ) {
            t = (1 + t * p) % mod;
        }
        res = (res * t) % mod;
    }
    
    cout << res << 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

最大公约数

在这里插入图片描述
d / a , d / b d/a,d/b d/ad/b,那么 d / ( a + b ) d/(a+b) d/(a+b),同理, d / ( a × x + b × y ) d/(a\times x + b \times y) d/(a×x+b×y)

⇒ d / ( a , b ) → d / ( b , a − c × b ) \Rightarrow d/(a,b) \rightarrow d/(b,a - c \times b) d/(ab)d/(bac×b)

#include <iostream>

using namespace std;

int gcd(int a,int b) {
    if(a < b) 
        return gcd(b,a);

    if(b == 0) return a;
    
    return gcd(b,a % b);
}

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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/609378
推荐阅读
相关标签
  

闽ICP备14008679号