数学知识

Created in March 07, 2025

2025   ·   code   algorithm   acwing   数学知识   ·   learning-notebook

质数

试除法判定质数

知识点

  • 质数：严格大于1的整数中，如果只包含一和本身这两个约数，就被称为质数/素数
    • 所有小于等于1的整数，既不是质数，也不是合数
  • 如果$d$能整除$N$， 那么$\frac{N}{d}$也能整除$N$，这其实就是$d \times \frac{N}{d} = N$的变形

解题思路

  • 暴力枚举：从2 ~ N - 1依次判断，看每个元素是否能整除N
  • 优化：根据知识点中的定理，我们枚举每一对成对出现的除数中较小的那一个
    • 例如：3和4之于12
    • 所以，我们的判断范围就缩小到了
      • $d \leq \frac{N}{d}$
      • 即$d \leq \sqrt{N}$
  • 时间复杂度是$\Omega(\sqrt{N})$

实现代码

#include <bits/stdc++.h>
using namespace std;

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

    return true;
}

int main(){
    int n;
    cin >> n;
    while(n --){
        int a;
        cin >> a;
        if(is_prime(a))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

    return 0;
}

分解质因数

知识点

  • $n$中最多只包含一个大于$\sqrt{N}$的质因子
  • 根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。\(n = p_1^{a_1}\times p_2^{a_2}\times ... \times p_n^{a_n}\)

解题思路

  • 从小到大，枚举所有的因子
  • 时间复杂度介于$\Omega(logN) \sim \Omega(\sqrt{N})$
  • 对于分解过程中，有没有可能分解出来合数的可能呢？
    • 假设我们枚举到了N
    • 那么从2 ~ N - 1的质因子已经被我们提取出来，包括能够合成N的质因子
    • 所以，我们不必担忧N为合数

实现代码


#include <bits/stdc++.h>
using namespace std;


void divide(int x){
    for(int i = 2; i <= x / i; i ++){
        if(x % i == 0){
            // 该质因数的次数
            int s = 0;
            while(x % i == 0){
                x /= i;
                s ++;
            }
            cout << i << ' ' << s << endl;
        }
    }
    // 如果最后x大于1，那么他就一定是大于sqrt(x)的那个质因数
    if(x > 1)
        cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main(){
    int n;
    cin >> n;
    while(n --){
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

筛质数

知识点

  • $1 \sim n$中有$\frac{n}{\ln n}$个质数

解题思路

  • 暴力解法：
    • 遍历数组中的每一个数字
    • 将这个数字的所有倍数删掉
    • 遍历整个数组结束之后，剩下的数字就是质数
    • 计算时间复杂度：$\frac{n}{2} + \frac{n}{3} +\dots+\frac{n}{n}$
      • 这可以看做调和级数
      • $\underset{n\rightarrow +\infty}{\lim}(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}) = \ln n + C$
      • 给定$n > 1$时，$\ln n < \log_2n$
      • 所以时间复杂度为$\Omega(n\log n)$
  • 埃氏筛法：
    • 只对质数的倍数进行遍历
    • 如果一个合数之前的所有质因子都被遍历过的话，那么这个合数一定被遍历
    • 时间复杂度：$\Omega(n\log \log n)$
  • 线型筛法：$n$只会被自己的最小质因子筛选掉
    • 每次筛选到一个质数，就将这个质数加入primes[]当中，每次循环中，将primes[]从头开始遍历，筛选出来的合数就为primes[] * i
    • 为了保证每个合数只被筛选一遍，就要保证每个合数都是被其最小质因数筛选出来的，要找出primes[j] * i的最小质因数
      • 当i % primes[j] == 0时，因为primes[j]是从小到大进行遍历的，所以primes[j]一定是primes[] * i的最小质因数
      • 当i % primes[j] != 0时，说明此时primes[j]小于i的所有质因子，所以此时primes[j]还是最小质因子
    • 保证每个合数都能被筛选掉
      • 对于一个合数x，假设pj是x的最小质因子，当i枚举到x / pj，这个合数就会被筛选掉

实现代码

暴力筛法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i])
            primes[cnt ++] = i;
        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }

}


int main(){
    int n;
    cin >> n;
    get_primes(n);

    cout << cnt << endl;
}

埃氏筛法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(st[i])
            continue;
        primes[cnt ++] = i;
        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }

}


int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
}

线型筛法


#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
int primes[N], cnt;
bool st[N];

void get_primes(int 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;
            // 如果此时不break的话，继续枚举就是primes[j + 1]了
            // 因为i % primes[j] == 0
            // 所以primes[j + 1] * i 的最小质因子还是primes[j]
            // 会出现重复筛选
            // 所以break
        }
    }

}


int main(){
    int n;
    cin >> n;
    get_primes(n);

    cout << cnt << endl;
}

约数

试除法求约数

知识点

解题思路

  • 同样采用试除法，我们只枚举每对除数（$d$和$\frac{N}{d}$）中较小的那一个
  • 然后再将较大的元素入vector，需要避免i * i = N的情况发生，推入时需要判断

实现代码


#include <bits/stdc++.h>
using namespace std;

vector<int> get_divisors(int x){
    vector<int> res;
    for(int i = 1; i <= x / i; i ++){
        if(x % i == 0){
            res.push_back(i);
            if(x / i != i)
                res.push_back(x / i);
        }
    }

    sort(res.begin(), res.end());

    return res;
}

int main(){
    int n;
    cin >> n;
    while(n --){
        int a;
        cin >> a;
        auto res = get_divisors(a);
        for(auto num: res)
            printf("%d ", num);
        cout << endl;
    }
    return 0;
}

约数个数

知识点

约数个数

  • 给定一个数$N$，如果$N$可以分解为\(N = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots \times p_n^{\alpha_n}\)
  • 那么该数的约数个数就有$(\alpha_1 + 1)(\alpha_2 + 1)\dots(\alpha_n + 1)$个
    • 因为$N$的任一质因数都可用下列公式表示\(x = p_1^{\beta_1} \times p_2^{\beta_2} \times \dots \times p_n^{\beta_n}\)
    • 其中$\beta_i$的取值范围为$[0, \alpha_i]$，所以一共有$(\alpha_1 + 1)(\alpha_2 + 1)\dots(\alpha_n + 1)$个组合
    • 即$(\alpha_1 + 1)(\alpha_2 + 1)\dots(\alpha_n + 1)$个约数

约数之和

  • 约数之和：\(Sum = (p_1^0+p_1^1+\dots+p_1^{\alpha_1})\dots(p_k^0 + p_k^1+\dots+p_k^{\alpha_k})\)

解题思路

实现代码


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 110, mod = 1e9 + 7;

int main(){
    int n;
    cin >> n;

    unordered_map<int, int> primes;

    while(n --){
        int a;
        scanf("%d", &a);


        for(int i = 2; i <= a / i; i ++){
            while(a % i == 0){
                a /= i;
                primes[i] ++;
            }
        }

        if(a > 1)
            primes[a] ++;
    }

    ll res = 1;


    for(auto p: primes)
        res = res*(p.second + 1) % mod;

    cout << res << endl;

    return 0;
}

约数之和

实现代码


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;


const int N = 110, mod = 1e9 + 7;
int n;


int main(){
    cin >> n;
    unordered_map<int, int> primes;
    while(n --){
        int a;
        scanf("%d", &a);

        for(int i = 2; i <= a / i; i ++){
            while(a % i == 0){
                a /= i;
                primes[i] ++;
            }


        }
        if(a > 1)
            primes[a] ++;
    }

    LL res = 1;
    for(auto p: primes){
        // b就是公式里面的\alpha_i
        LL a = p.first, b = p.second;
        LL t = 1;
        while(b --){
            t = (t * a + 1) % mod;
        }

        res = res * t % mod;
    }

    printf("%lld\n", res);

}

最大公约数

知识点

  • 欧几里得算法（辗转相除法）
  • 一些基本性质：
    • 如果$d$能整除$a$，也能整除$b$，那么$d$能整除$a + b$
    • 同时也能整除$x \times a + y \times b$
    • 例如：$2$能整除$4$，也能整除$6$；也能整除$10$，也能整除$14=2\times 4 + 6$

解题思路

  • 一个性质：如果$d$能够同时整除$a$和$b$，那么$d$也能同时整除$$和$a\ \% \ b$
    • 证明：
    • 因为$a\ \% \ b=a-\left\lfloor \frac{a}{b} \right\rfloor \times b = a - c\times b$
    • 所以我们可以转为证明：如果$d$为$a$和$b$的公因数，那么$d$也为$b$和$a-c\times b$的公因数
    • 给定$d$为$a$和$b$的因数，那么对$a-c\times b$做操作$a-c\times b + c\times b = a$
    • 则说明

实现代码

  • 一行代码模版
#include <bits/stdc++.h>
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 a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}

欧拉函数

欧拉函数

知识点

  • $\phi(n)$表示1~n中互质的数有多少个
  • $\phi(6)=2$

解题思路

  • 从1~N中去掉$p_1, p_2, \dots,p_k$的所有倍数
  • 加上所有$p_i \times p_j$的倍数

实现代码


#include <bits/stdc++.h>
using namespace std;

int n;

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

        cout << res << endl;
    }

    return 0;
}

求组合数

求组合数 I

知识点

  • $\mathrm{C}{a}^{b} = \mathrm{C}{a-1}^{b}+\mathrm{C}_{a-1}^{b-1}$

解题思路

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];


void init(){
    for(int i = 0; i < N; i ++){
        for(int j = 0; j <= i; j ++){
            if(j == 0)
                c[i][j] = 1;
            else
                c[i][j] = (c[i- 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
}


int main(){
    int n;
    cin >> n;
    init();
    while(n --){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }

    return 0;

}


Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Google Gemini updates: Flash 1.5, Gemma 2 and Project Astra
  • Displaying External Posts on Your al-folio Blog
  • 强化学习导论
  • 企业项目实训
  • 面试总结