08.01_基础数论

基础数论

问题描述

基础数论处理整数的基本性质和关系，包括质数判定、最大公约数、质因数分解等问题。

质数判定

算法思想

对于一个数n，只需要判断到sqrt(n)
可以通过筛法预处理优化判定
适用于单个数的判定
时间复杂度 $\mathcal{O}(\sqrt{n})$

代码实现

c++
java
python

class Solution {
public:
    bool isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    vector<bool> sieveOfEratosthenes(int n) {
        vector<bool> isPrime(n + 1, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        return isPrime;
    }
};

class Solution {
    public boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public boolean[] sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        return isPrime;
    }
}

class Solution:
    def isPrime(self, n: int) -> bool:
        if n < 2:
            return False
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True
    
    def sieveOfEratosthenes(self, n: int) -> List[bool]:
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
        
        return is_prime

最大公约数

算法思想

使用辗转相除法（欧几里得算法）
基于 gcd(a,b) = gcd(b,a%b)
可以扩展到求解线性方程
时间复杂度 $\mathcal{O}(\log n)$

代码实现

c++
java
python

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 扩展欧几里得算法
    tuple<int, int, int> exgcd(int a, int b) {
        if (b == 0) {
            return {a, 1, 0};
        }
        int d, x, y;
        tie(d, x, y) = exgcd(b, a % b);
        return {d, y, x - (a / b) * y};
    }
};

class Solution {
    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 扩展欧几里得算法
    public int[] exgcd(int a, int b) {
        if (b == 0) {
            return new int[]{a, 1, 0};
        }
        int[] result = exgcd(b, a % b);
        int d = result[0], x = result[1], y = result[2];
        return new int[]{d, y, x - (a / b) * y};
    }
}

class Solution:
    def gcd(self, a: int, b: int) -> int:
        return a if b == 0 else self.gcd(b, a % b)
    
    # 扩展欧几里得算法
    def exgcd(self, a: int, b: int) -> Tuple[int, int, int]:
        if b == 0:
            return a, 1, 0
        d, x, y = self.exgcd(b, a % b)
        return d, y, x - (a // b) * y

时间复杂度分析

算法时间复杂度空间复杂度

质数判定	$\mathcal{O}(\sqrt{n})$	$\mathcal{O}(1)$
埃氏筛	$\mathcal{O}(n \log \log n)$	$\mathcal{O}(n)$
欧几里得	$\mathcal{O}(\log n)$	$\mathcal{O}(1)$
扩展欧几里得	$\mathcal{O}(\log n)$	$\mathcal{O}(1)$

应用场景

质数判定
质因数分解
最大公约数
最小公倍数
线性方程求解

注意事项

数据范围的考虑
溢出的处理
特殊情况的判断
预处理的时机
算法的选择

常见变形

最小公倍数

cpp
java
python

long long lcm(int a, int b) {
    return (long long)a / gcd(a, b) * b;  // 使用long long防止溢出
}

class Solution {
    public long lcm(int a, int b) {
        return (long)a / gcd(a, b) * b;  // 使用long防止溢出
    }
}

class Solution:
    def lcm(self, a: int, b: int) -> int:
        return a // self.gcd(a, b) * b  # 使用整除防止浮点数

质因数分解

cpp
java
python

vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> factors;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            factors.emplace_back(i, cnt);
        }
    }
    if (n > 1) {
        factors.emplace_back(n, 1);
    }
    return factors;
}

class Solution {
    public List<int[]> factorize(int n) {
        List<int[]> factors = new ArrayList<>();
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                int cnt = 0;
                while (n % i == 0) {
                    cnt++;
                    n /= i;
                }
                factors.add(new int[]{i, cnt});
            }
        }
        if (n > 1) {
            factors.add(new int[]{n, 1});
        }
        return factors;
    }
}

class Solution:
    def factorize(self, n: int) -> List[Tuple[int, int]]:
        factors = []
        i = 2
        while i * i <= n:
            if n % i == 0:
                cnt = 0
                while n % i == 0:
                    cnt += 1
                    n //= i
                factors.append((i, cnt))
            i += 1
        if n > 1:
            factors.append((n, 1))
        return factors