竞赛编程中的数论

数论为竞赛编程提供了基本工具，包括GCD/LCM计算、模运算、质数和欧拉定理。这些概念在竞赛问题中经常出现，是高级算法的基础。

GCD和LCM

最大公约数（GCD）和最小公倍数（LCM）是数论中的基本运算，有许多应用。

GCD和LCM实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class NumberTheory {
public:
    // 欧几里得算法求GCD
    static long long gcd(long long a, long long b) {
        while (b != 0) {
            long long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // 使用GCD计算LCM
    static long long lcm(long long a, long long b) {
        return (a / gcd(a, b)) * b; // 避免溢出
    }
    
    // 扩展欧几里得算法
    static long long extendedGCD(long long a, long long b, long long& x, long long& y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        
        long long x1, y1;
        long long gcd_val = extendedGCD(b, a % b, x1, y1);
        
        x = y1;
        y = x1 - (a / b) * y1;
        
        return gcd_val;
    }
    
    // 模逆元
    static long long modInverse(long long a, long long m) {
        long long x, y;
        long long g = extendedGCD(a, m, x, y);
        
        if (g != 1) {
            return -1; // 逆元不存在
        }
        
        return (x % m + m) % m;
    }
    
    // 快速幂取模
    static long long powerMod(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;
        
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        
        return result;
    }
    
    // 数组的GCD
    static long long arrayGCD(vector<long long>& arr) {
        long long result = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            result = gcd(result, arr[i]);
            if (result == 1) break; // 优化
        }
        return result;
    }
    
    // 数组的LCM
    static long long arrayLCM(vector<long long>& arr) {
        long long result = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            result = lcm(result, arr[i]);
        }
        return result;
    }
};

int main() {
    // 测试基本GCD和LCM
    long long a = 48, b = 18;
    cout << "数字: " << a << ", " << b << endl;
    cout << "GCD: " << NumberTheory::gcd(a, b) << endl;
    cout << "LCM: " << NumberTheory::lcm(a, b) << endl;
    
    // 测试扩展GCD
    long long x, y;
    long long g = NumberTheory::extendedGCD(a, b, x, y);
    cout << "\n扩展GCD: " << g << endl;
    cout << "系数: x=" << x << ", y=" << y << endl;
    cout << "验证: " << a << "*" << x << " + " << b << "*" << y << " = " << (a*x + b*y) << endl;
    
    // 测试模逆元
    long long num = 3, mod = 11;
    long long inv = NumberTheory::modInverse(num, mod);
    cout << "\n模逆元 " << num << " 模 " << mod << ": " << inv << endl;
    if (inv != -1) {
        cout << "验证: " << num << "*" << inv << " ≡ " << (num * inv) % mod << " (mod " << mod << ")" << endl;
    }
    
    // 测试快速幂
    long long base = 2, exp = 10, modulo = 1000000007;
    long long power = NumberTheory::powerMod(base, exp, modulo);
    cout << "\n" << base << "^" << exp << " mod " << modulo << " = " << power << endl;
    
    // 测试数组操作
    vector<long long> arr = {12, 18, 24, 36};
    cout << "\n数组: ";
    for (long long x : arr) cout << x << " ";
    cout << endl;
    cout << "数组GCD: " << NumberTheory::arrayGCD(arr) << endl;
    cout << "数组LCM: " << NumberTheory::arrayLCM(arr) << endl;
    
    return 0;
}

这些基本数论运算使用高效算法：欧几里得算法求GCD（O(log min(a,b))），扩展GCD找系数，快速幂进行模运算（O(log n)）。

质数与因式分解

质数算法对许多竞赛编程问题至关重要，包括因式分解和素性测试。

质数与因式分解

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

class PrimeUtils {
public:
    // 埃拉托斯特尼筛法
    static 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;
    }
    
    // 获取n以内的所有质数
    static vector<int> getPrimes(int n) {
        vector<bool> isPrime = sieveOfEratosthenes(n);
        vector<int> primes;
        
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.push_back(i);
            }
        }
        
        return primes;
    }
    
    // 检查数字是否为质数（大数）
    static bool isPrime(long long n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (long long i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    // 质因数分解
    static map<long long, int> primeFactorization(long long n) {
        map<long long, int> factors;
        
        // 处理因子2
        while (n % 2 == 0) {
            factors[2]++;
            n /= 2;
        }
        
        // 处理奇数因子
        for (long long i = 3; i * i <= n; i += 2) {
            while (n % i == 0) {
                factors[i]++;
                n /= i;
            }
        }
        
        // 如果n仍然>1，那么它是质数
        if (n > 1) {
            factors[n]++;
        }
        
        return factors;
    }
    
    // 使用质因数分解计算因子数
    static long long countDivisors(long long n) {
        map<long long, int> factors = primeFactorization(n);
        long long count = 1;
        
        for (auto& [prime, power] : factors) {
            count *= (power + 1);
        }
        
        return count;
    }
    
    // 使用质因数分解计算因子和
    static long long sumOfDivisors(long long n) {
        map<long long, int> factors = primeFactorization(n);
        long long sum = 1;
        
        for (auto& [prime, power] : factors) {
            long long termSum = 0;
            long long primePower = 1;
            
            for (int i = 0; i <= power; i++) {
                termSum += primePower;
                primePower *= prime;
            }
            
            sum *= termSum;
        }
        
        return sum;
    }
    
    // 欧拉函数
    static long long eulerTotient(long long n) {
        map<long long, int> factors = primeFactorization(n);
        long long result = n;
        
        for (auto& [prime, power] : factors) {
            result = result / prime * (prime - 1);
        }
        
        return result;
    }
};

int main() {
    int n = 30;
    
    // 生成n以内的质数
    vector<int> primes = PrimeUtils::getPrimes(n);
    cout << "质数到 " << n << ": ";
    for (int p : primes) cout << p << " ";
    cout << endl;
    
    // 测试质数检查
    vector<long long> testNumbers = {17, 25, 97, 100};
    cout << "\n质数检查:" << endl;
    for (long long num : testNumbers) {
        cout << num << ": " << (PrimeUtils::isPrime(num) ? "质数" : "非质数") << endl;
    }
    
    // 测试因式分解
    long long factorNum = 60;
    cout << "\n质因数分解 " << factorNum << ": ";
    map<long long, int> factors = PrimeUtils::primeFactorization(factorNum);
    bool first = true;
    for (auto& [prime, power] : factors) {
        if (!first) cout << " × ";
        cout << prime;
        if (power > 1) cout << "^" << power;
        first = false;
    }
    cout << endl;
    
    // 测试因子函数
    cout << "因子数: " << PrimeUtils::countDivisors(factorNum) << endl;
    cout << "因子和: " << PrimeUtils::sumOfDivisors(factorNum) << endl;
    cout << "欧拉函数: " << PrimeUtils::eulerTotient(factorNum) << endl;
    
    return 0;
}

质数算法使用优化方法：多次查询用筛法O(n log log n)，试除法用6k±1优化，高效因式分解计算数论函数。

关键要点

欧几里得算法在O(log min(a,b))时间内提供高效的GCD计算
扩展GCD使模逆元计算和求解线性丢番图方程成为可能
埃拉托斯特尼筛法在O(n log log n)时间内高效找到n以内的所有质数
质因数分解使因子函数和数论性质的计算成为可能