唯一分解定理

唯一分解定理（Fundamental Theorem of Arithmetic） 是初等数论中一个非常重要的定理，它说明了自然数的基本结构。

定理内容

每个大于 1 的整数都可以表示为若干个素数的乘积，且这种表示是唯一的（不计顺序）。也就是说，对于任意整数 \(n > 1\)，存在唯一的一组素数 \(p_1, p_2, \dots, p_k\) 和相应的正整数次幂 \(a_1, a_2, \dots, a_k\)，使得：

\(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\)

其中 \(p_1 < p_2 < \cdots < p_k\)，每个 \(p_i\) 是素数，且唯一性意味着这组素数和指数是唯一确定的（顺序除外）。

分解模版

硬拆版

时间复杂度为 \(O(\sqrt{n})\)

// 分解质因数
void primeFactorize(map<int, int> &factors, int n){

    // 单独处理 2
    while (n % 2 == 0){
        factors[2]++;
        n /= 2;
    }

    // 处理奇数
    for (int i=3; i*i<=n; i+=2){
        while (n % i == 0){
            factors[i]++;
            n /= i;
        }
    }

    // 如果最后剩下一个大于1的数 它是素数
    if (n > 1) factors[n]++;
}

优化版

通过预处理线性筛法 求出每个数的最小质因子，再通过它实现快速分解

构建lpf数组: \(O(n)\)
单个数分解质因数配合lpf: \(O(log_n)\)
所有数 1～n分解: \(O(nlog_n)\)

void compute_lpf(vector<int> &primes, map<int, int> &lpf, int n){
    for (int i=2; i<=n; i++){
        if (!lpf[i]){
            lpf[i] = i;
            primes.push_back(i);
        }

        for (int p: primes){
            if (p > lpf[i] || i*p > n) break;
            lpf[i*p] = p;
        }
    }
}

void primeFactorize(map<int, int> &factors, map<int, int> &lpf, int n){
    while (n > 1){
        int p = lpf[n];   // 找 n的最小质因子
        factors[p]++;
        n /= p;
    }
}

vector<int> primes;
map<int, int> lpf;
map<int, int> factors;

compute_lpf(primes, lpf, 2000);
primeFactorize(factors, lpf, 1892);

for (auto p: factors){
    cout << p.first << " " << p.second << endl;
}

约数与因数个数计算

一个数的因数个数可以由其素因数分解式推出： - 若 \(n = p_1^{a_1} \cdot p_2^{a_2} \cdot \dots \cdot p_k^{a_k}\) - 则因数个数为 \((a_1+1)(a_2+1)\dots(a_k+1)\)

为什么要加上1? - 因为指数可以取到 0，例如 \(a^0\)

// 求因数
int countDivisors(int n){
    int ret = 1;
    for (int i=2; i*i<=n; i++){
        int cnt =0;
        while (n % i == 0){
            cnt++;
            n /= i;
        }
        ret *= (cnt+1);
    }
    if (n > 1) ret*=2;
    return ret;
}

GCD 与 LCM

GCD：只保留两者都包含的素因子，幂次取最小
LCM：合并所有素因子，幂次取最大

步骤： \(a = 60, b = 48\)

\(60 = 2^2 \cdot 3^1 \cdot 5^1\)
\(48 = 2^4 \cdot 3^1\)
\(GCD = 2^{min(2, 4)} × 3^{min(1, 1)} = 2^2 × 3^1 = 4 × 3 = 12\)
\(LCM = 2^{max(2, 4)} × 3^{max(1, 1)} × 5^{max(1, 0)} = 2^4 × 3^1 × 5^1 = 16 × 3 × 5 = 240\)

判断是否为平方数、立方数等

若一个数的所有素因子的幂次都是偶数，则是完全平方数。