题解 - P5973
STA_Morlin
·
·
题解
P5973 [PA2013] Iloczyn の 题目传送门。
题目简化
RT，题目足够简单。
思路讲解
黄至绿，DFS。
刚开始是想用 DP 做的，不会推方程……
然后发现 STD 就是 DFS……
首先可以看到 n 的范围是 1 至 10^9，再计算一下 20! \thickapprox 2 \times 10^{18}，经过二分可以快速得到在 k = 13 时，已经无法拆分 n 了 (13! \thickapprox 6 \times 10^9)。
为了更加速度，我们还可以推算出来，只有在 k \le n 时，才可以拆分，可以自证，不进行详解。
容易知道，希望划分的 k 个数一定是 n 的约数，所以应先求其约数。
代码实现
我们知道极限数据是 4 \times 10^{12}，如果是直接使用从 1 至 n 的循环会 T 飞掉。
但容易知道，除平方数以外，所有自然数都具有偶数个因数，并且平均分布在 \sqrt n 两侧。可以反证：若某一侧比另一侧含有更多的因数，那么将无法成功配对，将有某两个因数的乘积大于或小于 n。
这样就可以求约数了，\sqrt {10^9} \thickapprox 3 \times 10^4。
CODE
fors(i, 1, i <= sqrt(n), 1)
if (!(n%i)) {
a.push_back(i);
if (i*i != n) a.push_back(n/i);
}
sort(a.begin(), a.end());
求完约数就可以写 dfs 了。
约定：
$p$ 代表还需要除以 $p$ 才能将 $n$ 除尽。
$m$ 代表正在考虑第 $m$ 个约数。
首先从 $k, n, 0$ 开始。
终止条件：$d = 0$。
然后判断剩余的约数能否被取走。
因为在前面排了序，所以接下来的一定是比后面更小的，如果前面小的都除不尽的话就说明大的也没戏。
### _CODE_
```cpp
int l = d, u = 1;
fors(i, m, i<a.size() && l--, 1) if ((u*=a[i]) > p) return 0;
```
接下来挨个找可以被整除的约数。
$u$ 代表的是接下来 $d$ 个约数的积。
### _CODE_
```cpp
fors(i, m, i<a.size() && && i+d-1<=a.size() && u<=p, 1) {
if (i != m) u = u/a[i-1]*a[i];// 如果不是第一个且 a[i-1] 不符合要求，就代表接下来还需要 a[i]。
if (!(p%a[i]) && dfs(d-1, p/a[i], i+1)) return 1;// 如果 p 能整除 a[i] 且 a[i] 配对成功的话就说明可行，直接真值返回。
}
```
# E.N.D.