本文共 8543 字，大约阅读时间需要 28 分钟。

质数

概念 : 在大于1的整数中 , 如果只包含1和本身这两个约数 , 就被称为质数 , 或者称作素数.

质数的判定 – 试除法 :

时间复杂度 : O ( sqrt(n) )

d | n --> n/d | n ( “|” 表示整除 )

只需判断较小的那个约数 , d^2 <= n ( d <= sqrt(n) )–> d <= n/d

注意 : 这里在循环中的退出条件一般写成 i <= n / i , 不推荐使用 sqrt函数 , 因为每次循环都需要调用一遍 sqrt函数 , 而sqsrt函数的速度较慢 , 导致整体速度较慢.

也不推荐使用 i * i <= n , 因为当数据接近于 int型的时候很有可能会溢出.

代码如下 :

bool is_prime(int x){
       if(n < 2) return false ;     for(int i = 2;i < n / i;i ++ )        if(n % i == 0)             return false ;     return true ; }

分解质因数 – 试除法 :

原理 : n 中最多只包含一个大于 sqrt(n) 的质因子

时间复杂度 : 最好情况 (n == 2^k): log ( n ) 最坏情况 : sqrt( n )

思路 : 从小到大枚举所有数

关于为什么不会筛到合数的原因 : 因为我们这里是从小到大进行枚举的 , 一旦可以整除 , 就一直除直到不能除为止 , 所以当枚举到第 i 个数的时候 , 其前面的 i - 1 个数的质因子已全被筛去 , 此时如果其能够被 x 整除 , 那么它必然就是 x 的一个质因子 . 原理同埃筛.

代码如下 :

void divide(int x){
       for (int i = 2; i <= x / i; i ++ )        if (x % i == 0) // i 一定是质数        {
               int s = 0;            while (x % i == 0) x /= i, s ++ ;            cout << i << ' ' << s << endl;        }    if (x > 1) cout << x << ' ' << 1 << endl; // 大于 sqrt(n) 的质因子    cout << endl;}

线性筛法求素数

原理 : 将所有的数写到一个数表中 , 从小到大遍历 , 将每一个数的所有倍数删去 , 遍历完成后 , 所有剩下的数都为质数 .

假设对于任意一个数 p 而言 , 如果其没有被删去 , 则说明 2 ~ p-1 中没有一个数是它的因子 , 所以此时只有 1 和 它本身是它的因子 , 因此其为质数.

代码如下 :

朴素筛法(埃筛) – 优化后 :

其思想很重要 , 可以进行推广.

原理 : 当枚举到 p 时 , 只需要判断 p 之前的 2 ~ p-1 中的质数是不是p的因子即可 , 不需要所有数全部判断一遍 , 因为 , 在此之前其所有非质数的数会被全部删去 .

只需要删去所有质数的倍数的数 , 而不需要删去不是质数的倍数的数 ( 这样会造成重复删除 , 效率减慢 )

质数定理 : 在 1 ~ n 当中 , 有 ( n / log n ) 个质数

因此在枚举的时候 , 只需枚举 2 ~ log n , 也就是枚举 logn 个数.

时间复杂度 : O ( n ) (粗略估计情况) 真实情况 : O ( n*log(logn) )

#include 
   
    #include 
    
     using namespace std ;const int N = 1000010 ; int primes[N] , cnt ; // cnt 用来给素数表计数bool st[N] ; // 用来判定一个数是否被删去// 朴素筛法 :void get_primes(int n){
       for(int i = 2;i <= n;i ++ ) // 遍历 i ~ n 数表    {
           if (!st[i]) // 如果该数没有被删去        {
               primes[cnt ++ ] = i ; // 将其加入到素数表中            for(int j = i + i;j <= n;j += i) st[j] = true ; // 将所有质数i的倍数的数删去        }    }}int main(){
       get_primes(1000) ;    for(int i = 0;i < cnt;i ++ ) printf("%d ",primes[i]) ;    cout << endl ;    return 0 ;}
    
   

线性筛法:

原理 : 争取将每一个合数用其质因子筛掉

可以将其与上述的 埃筛 进行对比

n 只会被它的最小质因子筛掉

1. i % primes[j] == 0

   primes[j] 一定是 i 的最小质因子 , primes[j] 也一定是 primes[j] * i 的最小质因子

2. i % primes[j] != 0 , 因此 primes[j] 一定小于 i 的所有质因子 , 所以 primes[j] 也一定是 primes[j] * i 的最小质因子

综合以上两点 , 可得出该结论 : 每一个被筛掉的数都一定是被其最小质因子给筛掉的

对于一个合数 x , 其一定存在一个最小质因子 , 假设 primes[j] 是 x 的最小质因子 , 当 i 枚举到 x / primes[j] 的时候 , 都一定会被筛掉 , 在 i 枚举到 x 之前.

并且每次筛的时候都用其最小质因子来筛 , 又因为每个数只有一个最小质因子 , 因此每个数只会被筛一次 , 因此其是线性的.

时间复杂度 ; O ( n )

void get_primes(int n){
       for (int i = 2; i <= n; i ++ )    {
           if (!st[i]) primes[cnt ++ ] = i;        // 不需要加 j < cnt 这个条件,当 i 为质数的时候 , primes会在最小质因子的时候停下,当i为质数的时候,primes会在枚举到该轮的质数的时候停下来 , 即 primes[j]^2 <= n         for (int j = 0; primes[j] <= n / i; j ++ ) // 注意这里的跳出条件        {
               st[primes[j] * i] = true; // 删去所有质数倍数的数字,且这个数会小于我们给定的 n ,            // 如果 i 是质数的话 , 就处理 , 否则不进行删除操作(重复)            // 因为在此算法中 , 我们仅仅删去质数倍数的数            if (i % primes[j] == 0) break; // primes[j]一定是i的最小质因子        }    }}

约数

基本概念 : 约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

试除法求一个数的所有约数 :

原理: d | n --> n/d | n 一个数的约数是成对出现的 , 我们在枚举的时候枚举较小的那个约数即可 , 枚举到满足 d <= n/d --> d <= sqrt(n)

从小到大枚举小的那个约数 , 注意判断边界情况,.

时间复杂度 : sqrt(n)

代码如下 :

#include 
   
    #include 
    
     #include 
     
      using namespace std ;vector
      
        get_divisors(int n){
       vector
       
         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) ; // 这里一定要判断边界情况 : i^2 == n        }    }    sort(res.begin() , res.end()) ; // 对约数数组进行从小到大排序    return res ;}int main(){
       int n ; cin >> n ;    while (n -- )    {
           int x ;        cin >> x ;        auto res = get_divisors(x) ;        for (auto t : res) cout << t << " " ;        cout << endl ;    }    return 0 ;}
       
      
     
    
   

约数个数 :

算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

例如: 6936 = 2^3 * 3 * 17^2 , 1200 = 2^4 * 3 * 5^2

算术基本定理的内容由两部分构成：

1.分解的存在性：

2.分解的唯一性，即若不考虑排列的顺序，正整数分解为素数乘积的方式是唯一的。

$$公式:N={P_1}^{x_1}\cdot {P_2}^{x_2}\cdot ...\cdot {P_k}^{x_k}$$

$$约数个数公式:(X_1+1)\cdot (X_2+1)\cdot ...\cdot (X_k+1)$$

公式解释 :

注意 : 此公式下所用到的其因子全为质因子 , 因为其他非质的因子可以通过质因子的倍数来累乘得到

N 的任意一个约数 d 也可以写成 d = $P{1}^{B_1}$ * ${P_2}^{B_2}$ * … * ${P_k}^{B_k}$ 的形式,

每一个 Bi 都是在 0 ~ Xi 之间的 , 并且每一项 Bi 的指数不同的话 , 这个约数就不同.

因此 , 所有的约数个数就和 Bi 的取法的个数相同.

$例如:6=2^1\times 3^1$

此时其约数个数为 (1 + 1) * (1 + 1) = 4 ;

因为每一位有 0 ~ n 种取法 , 所以为 n + 1

int 范围内 , 约数个数最多的数的约数为1650个左右

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

输入样例 :

3

2

6

8

输出样例 :

12

代码如下 :

//  给定 n 个正整数 $a_i$ , 请输出这些数的乘积的约数的个数//  map key存底数 value存每个质因子的指数#include 
   
    #include 
    
     #include 
     
       // 使用hash表(unordered_map)需要包含这个头文件using namespace std ;const int mod = 1e9 + 7 ;typedef long long LL ;int main(){
       int n ; cin >> n ;    unordered_map
      
        primes ;    while (n -- )    {
           int x ; cin >> x ;        for(int i = 2;i <= x / i; i ++ )        {
               if (x % i == 0)            {
                   while (x % i == 0)                {
                       x /= i ;                    primes[i] ++ ;                }            }        }        if (x > 1) primes[x] ++ ;    }    LL res = 1 ;    for (auto prime : primes) res *= (prime.second + 1) % mod ;    cout << res << endl ;    return 0 ;}
      
     
    
   

约数之和 :

$$公式:N={P_1}^{x_1}\cdot {P_2}^{x_2}\cdot ...\cdot {P_k}^{x_k}$$

$$约数之和公式:({P_1}^0+P_1^1+...{P_1}^{X_1})\cdot ...\cdot (P_k^0+...+{P_k}^{X_k})$$

公式解释 : 将该式展开后可知其一定是一堆乘积的形式 , 这样的乘积有 约数个数 之个 , 等于从每个括号里面选一个数进行相乘 , 最终得到的每个乘积的形式均为 : $N={P_1}^{x_1}\cdot {P_2}^{x_2}\cdot ...\cdot {P_k}^{x_k}$ ,因此我们可以知道每个乘积的结果都是一个约数 ,也就是每一项都是一个约数,每一项又各不相同, 这些数的总数又等于约数的个数,所以所有的乘积之和就是所有的约数之和 .

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

与上述求约数的代码大体一致,先分解质因子 , 只是最后一步公式不一样

输入描述 :

3

2

6

8

输出描述 :

252

约数之和公式可以化简为 : 1 + $p^1$ + $p^2$ + … + $p^n$ = t*p + 1 ; 就是不断提一个因子出来到括号外面,不断提一直到不能够提为止

代码如下 :

//  给定 n 个正整数 $a_i$ , 请输出这些数的乘积的约数之和//  map key存底数 value存每个质因子的指数#include 
   
    #include 
    
     #include 
     
       // 使用hash表(unordered_map)需要包含这个头文件using namespace std ;const int mod = 1e9 + 7 ;typedef long long LL ;int main(){
       int n ; cin >> n ;    unordered_map
      
        primes ;    while (n -- )    {
           int x ; cin >> x ;        for(int i = 2;i <= x / i; i ++ )        {
               if (x % i == 0)            {
                   while (x % i == 0)                {
                       x /= i ;                    primes[i] ++ ;                }            }        }        if (x > 1) primes[x] ++ ;    }    LL res = 1 ;    for (auto prime : primes)    {
           LL t = 1 ;        int p = prime.first , a = prime.second ; // p代表这个质数的底数,a代表这个质数的指数        while (a -- ) t = (t * p + 1) % mod ;        res = res * t % mod ;    }    cout << res << endl ;    return 0 ;}
      
     
    
   

最大公约数 :

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

数论中的一些基本性质 : d | a , d | b --> d | a + b --> ax + by 符号 “|” 表示整除

核心原理 :

gcd(a,b) = gcd(b,a mod b) ---- a和b的最大公约数等于b和 a mod b 的最大公约数

a mod b == a - a/b(向下取整) * b = a - c * b

解释 : 对于任意一个公约数 d , d | a , d | b ; – > d | b , d || (a - b*c) ,因此(a , b) = (b , a - c * b )

因此左边的任何一个公约数都是右边的公约数

所以这两个公约数的集合是相同的,因此左边的最大公约数等于左边的最大公约数

利用此性质计算最大公约数

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

输入样例 :

2

3 6

4 6

输出样例 :

3

2

代码如下 :

#include 
   
    using namespace std ; int gcd(int a,int b){
       return b ? gcd(b,a % b) : a ; // 当 b = 0 时, 此时即求 a 和 0 的最大公约数,即为 a}int main(){
       int n ; cin >> n ;     while (n -- )    {
           int a , b ; cin >> a >> b ;         printf("%d \n",gcd(a,b)) ;     }    return 0 ; }
   

核心代码 ;

int gcd(int a,int b){
       return b ? gcd(b,a % b) : a ; // 当 b = 0 时, 此时即求 a 和 0 的最大公约数,即为 a}

转载地址：https://blog.csdn.net/weixin_45877540/article/details/109117626 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！