1628：X-factor Chain

题目描述

输入正整数 $x$，求 $x$ 的大于 $1$ 的因子组成的满足任意前一项都能整除后一项的序列的最大长度，以及满足最大长度的序列的个数。

输入格式

多组数据，每组数据一行，包含一个正整数 $x$。

输出格式

对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

样例

样例输入 #1

2
3
4
10
100

样例输出 #1

1 1
1 1
2 1
2 2
4 6

样例解释 #1

• $x=2$：因子大于 $1$ 的有 $\{2\}$，序列最大长度为 $1$，个数为 $1$。
• $x=3$：类似，长度为 $1$，个数为 $1$。
• $x=4$：因子大于 $1$ 的有 $\{2,4\}$，可以组成序列 $[2,4]$（因为 $2 \mid 4$），长度为 $2$，个数为 $1$（只有这一种顺序）。
• $x=10$：因子大于 $1$ 的有 $\{2,5,10\}$，可以组成序列 $[2,10]$ 或 $[5,10]$，长度为 $2$，个数为 $2$。
• $x=100$：因子大于 $1$ 的有许多，最大长度序列的例子：$[2,4,20,100]$ 或 $[5,10,50,100]$ 等。最大长度为 $4$，个数为 $6$。

数据范围

对于全部数据，$1 \le x \le 2^{20}$（即 $x \le 1048576$）。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要构造一个因子序列 $a_1, a_2, \dots, a_k$，满足 $a_i \mid a_{i+1}$ 且每个 $a_i > 1$，且都是 $x$ 的因子。要求最大长度 $k$ 以及达到最大长度的序列个数。

显然，序列的第一个元素可以是 $x$ 的任意大于 $1$ 的因子。但为了最大化长度，我们应该每次乘以一个质因子（或质因子的幂）来逐步增加。实际上，最大长度等于 $x$ 的质因子指数之和（即 $x$ 的总质因子个数，重复计算）。设 $x = p_1^{e_1} p_2^{e_2} \dots p_m^{e_m}$，则总质因子个数 $L = e_1 + e_2 + \dots + e_m$。序列可以从 $1$ 开始（但题目要求大于 $1$，所以从最小的质因子开始），每次乘以一个质因子，最终到达 $x$，这样序列长度就是 $L$。但题目要求序列中的每个数都是 $x$ 的因子，且大于 $1$。所以序列长度最大为 $L$。

接下来求满足最大长度的序列个数。这相当于将 $L$ 个质因子（有重复，因为同一质因子可能出现多次）排成一个序列，使得每个质因子按顺序乘起来得到的因子序列满足整除关系。实际上，序列 $a_1, a_2, \dots, a_L$ 满足 $a_{i} \mid a_{i+1}$，且 $a_1 > 1$，$a_L = x$。我们可以将质因子乘积累积，即 $a_i$ 是前 $i$ 个质因子的乘积。但质因子的顺序可以任意排列，只要保证对于每个质因子 $p$，它的 $e$ 次出现是连续的（因为如果中间插入了其他质因子，那么乘以部分 $p$ 后得到的因子不一定整除乘以更多 $p$ 后的因子？实际上，如果 $a$ 包含 $p$ 的 $k$ 次幂，$b$ 包含 $p$ 的 $k'$ 次幂且 $k' > k$，那么 $a \mid b$ 还需要其他质因子的指数也满足条件。所以我们需要保证序列中每个因子都是前一个因子乘以一个质因子（可以是任意质因子，但每个质因子的所有出现必须按顺序？）。更一般地，序列等价于一个多重集的排列，使得乘积前缀是递增的因子。这其实就是将 $L$ 个质因子（有标号？）排成一列，但相同质因子不可区分。因此，序列个数等于多重集的全排列数：$L! / (e_1! e_2! \dots e_m!)$。

验证样例：

• $x=4=2^2$，$L=2$，$e_1=2$，序列个数 $= 2! / 2! = 1$，正确。
• $x=10=2^1 \cdot 5^1$，$L=2$，$e_1=1, e_2=1$，序列个数 $= 2! / (1!1!) = 2$，正确。
• $x=100=2^2 \cdot 5^2$，$L=4$，$e_1=2, e_2=2$，序列个数 $= 4! / (2!2!) = 6$，正确。

所以算法步骤：

1. 对 $x$ 分解质因数，得到每个质因子的指数 $e_i$。
2. 计算 $L = \sum e_i$。
3. 计算序列个数 $ans = L! / \prod (e_i!)$。
4. 输出 $L$ 和 $ans$。

注意 $x$ 最大 $2^{20}$，$L$ 不会太大（因为 $2^{20}$ 的质因子只有 $2$，$L=20$）。但 $x$ 可能有多个质因子，$L$ 最多约为 $\log_2 x$ 乘以质因子个数，但 $x \le 1048576$，$L$ 最大可能为 $20$（当 $x=2^{20}$ 时）。所以计算阶乘可以直接用 long long（$20!$ 在 long long 范围内）。但注意 $x$ 可能不是 $2$ 的幂，例如 $x=9699690$（前几个质数乘积）可能使 $L$ 更大？但 $x \le 1048576$，质因子乘积增长快，$L$ 不会超过 $20$ 太多。稳妥起见，可以用 long long 计算。

注意多组数据，直到 EOF。