樱花 唯一质因子分解、线性筛

📕 | 知识点：线性筛、唯一质因子分解(阶乘分解)

求不定方程： 1 x + 1 y = 1 n ! \frac{1}{x}+\frac{1}{y}=\frac{1}{n!} x1​+y1​=n!1​ 的正整数解 ( x , y ) (x,y) (x,y) 的数目。

首先分析题目， x , y ∈ N ∗ x,y \in N* x,y∈N∗，求解组数。

对于题目给定的方程，由于都是分数形式，很难直接找出规律，因此先对方程进行变形，将分式相加转换为多项式： 1 x + 1 y = 1 n ! , x + y x y = 1 n ! , x = y ∗ n ! y − n ! , x = n ! + n ! 2 y − n ! , x − n ! = n ! 2 y − n ! , ( x − n ! ) ( y − n ! ) = n ! 2    ① \frac1x + \frac1y = \frac{1}{n!},\\ \frac{x + y}{xy} = \frac1{n!},\\ x = \frac{y*n!}{y - n!},\\ x = n ! + \frac{n!^2}{y - n!},\\ x - n! = \frac{n!^2}{y - n!},\\ (x - n!)(y - n!) = n!^2\ \ ① x1​+y1​=n!1​,xyx+y​=n!1​,x=y−n!y∗n!​,x=n!+y−n!n!2​,x−n!=y−n!n!2​,(x−n!)(y−n!)=n!2  ① 最后得到 ( x − n ! ) ( y − n ! ) = n ! 2 (x - n!)(y - n!) = n!^2 (x−n!)(y−n!)=n!2，因此可知 1 x < 1 n !   & &   1 y < 1 n ! \frac 1x < \frac1{n!} \ \&\& \ \frac 1y < \frac1{n!} x1​ n ! x > n!\ \&\&\ y > n! x>n! && y>n!

因此可以设 y = n ! + k   ( k ∈ N ∗ ) y = n! + k\ (k \in N*) y=n!+k (k∈N∗)，带入 ① ① ①式得 x = n ! 2 k + n !    ② x = \frac{n!^2}{k} + n! \ \ ② x=kn!2​+n!  ②

因为 x , y ∈ N ∗ x, y \in N* x,y∈N∗，因此对于 ② ② ②中 n ! 2 k ∈ N ∗ \frac{n!^2}{k} \in N* kn!2​∈N∗必成立，则题目转化为求 k k k使得 n ! 2 k \frac{n!^2}{k} kn!2​为正整数，即：求 n ! 2 n!^2 n!2的因子个数。

这里需要引入唯一质因子分解定理：

任何一个大于1的自然数 N N N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 N = P 1 a 1 P 2 a 2 P 3 a 3 . . . . . . P n a n N=P_1^{a_1}P_2^{a_2}P_3^{a_3}......P_n^{a_n} N=P1a1​​P2a2​​P3a3​​......Pnan​​，这里 P 1 < P 2 < P 3 . . . . . . < P n P_1