算术基本定理（唯一分解定理）：任何一个大于 $1$ 的自然数 $N$，如果 $N$ 不为质数，那么 $N$ 可以唯一分解成有限个质数的乘积 $N=P_1^{a_1}P_2^{a_2}P_3^{a_3}\cdots P_n^{a_n}$，$P_1<P_2<P_3<\cdots<P_n$ 且均为质数，$a_1,a_2,a_3,\cdots,a_n$ 均为正整数。

定理推论

  • 一个大于 $1$ 的整数 $N$，如果它的标准分解式为 $N=P_1^{a_1}P_2^{a_2}P_3^{a_3}\cdots P_n^{a_n}$，那么它的正因数个数为 $\sigma_0(N)=(1+a_1)(1+a_2)\cdots(1+a_n)$

简单证明：

$P_1^{b_1}P_2^{b_2}P_3^{b_3}\cdots P_n^{b_n}\ (0\leq b_1\leq a_1,0\leq b_2\leq a_2,\cdots)$ 一定是 $N$ 的正因数。其中 $b_1$ 可选 $[0,a_1]$ 共 $1+a_1$ 种，$b_2$ 可选 $[0,a_2]$ 共 $1+a_2$ 种 $\cdots\cdots$

根据乘法原理，整体选法总数为：$(1+a_1)(1+a_2)\cdots(1+a_n)$。每一种选法对应一个正因数，则选法数量就是正因数的个数。

  • 它的全体正因数之和为 $\sigma_1(N)=(P_1^0+P_1^1+P_1^2+\cdots+P_1^{a_1})(P_2^0+P_2^1+P_2^2+\cdots+P_2^{a_2})\cdots(P_n^0+P_n^1+P_n^2+\cdots+P_n^{a_n})$

简单证明：

我们将 $(P_1^0+P_1^1+P_1^2+\cdots+P_1^{a_1})(P_2^0+P_2^1+P_2^2+\cdots+P_2^{a_2})\cdots(P_n^0+P_n^1+P_n^2+\cdots+P_n^{a_n})$ 使用分配律展开，会得到一个多项式。

多项式中每个单项式的结构均为 $P_1^{b_1}P_2^{b_2}P_3^{b_3}\cdots P_n^{b_n}\ (0\leq b_1\leq a_1,0\leq b_2\leq a_2,\cdots)$，即 $N$ 的一个正因数。多项式的值便是所有正因数的和。

常见题型

求正因数个数

需要先用到欧拉筛生成质数，然后用质数从小到大分解 $N$ 得到 $a_1,a_2,a_3,\cdots,a_n$，然后计算出正因数个数 $\sigma_0(N)=(1+a_1)(1+a_2)\cdots(1+a_n)$

bool is_prime[SIZE];
int prime[SIZE], primesize = 0;
// 欧拉筛生成质数代码省略
int fact_cnt(int n)
{
    int now = n, ans = 1;
    for (int i = 0; i < primesize && prime[i] <= sqrt(now); i++)
    {
        int cnt = 0;
        while (now % prime[i] == 0)
        {
            cnt++;
            now /= prime[i];
        }
        ans *= (cnt + 1);
    }
    if (now != 1)
        ans *= 1 + 1;
    return ans;
}

判断正因数之和奇偶性

需要以下结论：

  • 奇数个奇数相加为奇数，偶数个奇数相加为偶数
  • 奇数乘奇数为奇数，奇数乘偶数为偶数，偶数乘偶数为偶数
  • 除了 $2$，质数均为奇数。因此除了 $2$，质数的任意次幂都是奇数。

假设 $\sigma_1(N)=(1+P_1+P_1^2+\cdots+P_1^{a_1})(1+P_2+P_2^2+\cdots+P_2^{a_2})\cdots(1+P_n+P_n^2+\cdots+P_n^{a_n})$ 为奇数，那么：

情况 1：若 $2\mid N$，那么 $P_1=2$，所以 $P_1+P_1^2+\cdots+P_1^{a_1}$ 为偶数，$1+P_1+P_1^2+\cdots+P_1^{a_1}$ 为奇数。

如果 $\sigma_1(N)$ 为奇数，那么 $(1+P_2+P_2^2+\cdots+P_2^{a_2}),\cdots,(1+P_n+P_n^2+\cdots+P_n^{a_n})$ 均为奇数

即 $(P_2+P_2^2+\cdots+P_2^{a_2}),\cdots,(P_n+P_n^2+\cdots+P_n^{a_n})$ 均为偶数

因为 $P_2,\cdots,P_n$ 均为质数，由结论可知，一定是偶数个奇数相加，即 $a_2,\cdots,a_n$ 均为偶数

情况 1.1：若 $a_1$ 为偶数，$N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdots P_n^{a_n}=(P_1^{a_1/2}\cdot P_2^{a_2/2}\cdot P_3^{a_3/2}\cdots P_n^{a_n/2})^2$ 为完全平方数 $x^2$

情况 1.2：若 $a_1$ 为奇数， $N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdots P_n^{a_n}=P_1\times(P_1^{(a_1-1)/2}\cdot P_2^{a_2/2}\cdot P_3^{a_3/2}\cdots P_n^{a_n/2})^2$ 为完全平方数的两倍 $2\cdot x^2$

情况 2：若 $2\nmid N$，同上得 $(P_1+P_1^2+\cdots+P_1^{a_2}),\cdots,(P_n+P_n^2+\cdots+P_n^{a_n})$ 均为偶数

所以 $N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdots P_n^{a_n}=(P_1^{a_1/2}\cdot P_2^{a_2/2}\cdot P_3^{a_3/2}\cdots P_n^{a_n/2})^2$ 为完全平方数 $x^2$

综上所述：若 $N=x^2\ 或\ 2\cdot x^2$，$\sigma_1(N)$ 为奇数，反之为偶数。

代码实现非常简单，略去。