唯一分解定理

（本文内容由AI生成，请审慎阅读）

任何大于 1 的正整数，都可以唯一写成质数相乘（不计顺序），是数论的基石，和欧几里得算法配套使用。

定理公式

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

• \(p_1<p_2<\dots<p_k\)：互不相同的质数
• \(a_1,a_2\dots a_k\)：正整数，叫指数
• 1 约定：没有质因子，是空乘积

例子：\(60=2^2 \times 3^1 \times 5^1\)

📌 三大竞赛推论（必考！）

设 \(n=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}\)

1. 约数个数定理

\(d(n)=(a_1+1)(a_2+1)\dots(a_k+1)\) 每个质数可以选 \(0,1\dots a_i\) 次，所以 + 1。 例：60，\((2+1)(1+1)(1+1)=12\) 个正约数。

2. 约数和定理

\(\sigma(n)=(1+p_1+p_1^2+\dots+p_1^{a_1})\times(1+p_2+p_2^2+\dots+p_2^{a_2})\dots\) 例：\(60=(1+2+4)(1+3)(1+5)=7\times4\times6=168\)

3. 用分解式求 gcd、lcm \(a=\prod p_i^{x_i},\ b=\prod p_i^{y_i}\)

• \(\gcd(a,b)=\prod p_i^{\min(x_i,y_i)}\)
• \(\text{lcm}(a,b)=\prod p_i^{\max(x_i,y_i)}\)

这就是为什么 \(\gcd(a,b)\times \text{lcm}(a,b)=a\times b\)

🐍 Python 模板（试除法分解质因数，竞赛最常用）

思路：从小到大试除，除到不能整除，记录质数和指数；最后如果剩下的 n>1，它本身是质数。

def factor(n):
    res = {}
    i = 2
    while i*i <= n:
        while n % i == 0:
            res[i] = res.get(i,0)+1
            n //= i
        i += 1
    if n > 1:
        res[n] = 1
    return res

# 测试
print(factor(60))  # {2:2,3:1,5:1}

用分解结果求约数个数

def count_div(fac):
    ans = 1
    for exp in fac.values():
        ans *= (exp+1)
    return ans

fac = factor(60)
print(count_div(fac))

⚠️ 竞赛坑点

1. 试除法只适合单个数分解；要批量分解很多数，改用埃氏筛 / 线性筛（欧拉筛）预处理最小质因子
2. 注意区分：质数、质因子、指数
3. 判断完全平方数：所有质因子指数都是偶数
4. 大数试除会慢；CSP-J 范围内这个试除法足够用