自动搬运

查看原文

来自洛谷，原作者为

	STA_Morlin 命运可以被相信，但不能被期待。

搬运于2025-08-24 22:16:07，当前版本为作者最后更新于2022-08-20 12:28:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 了。

约定：

$d$ 代表还需要 $d$ 个数才能达到 $k$ 个数。
$p$ 代表还需要除以 $p$ 才能将 $n$ 除尽。
$m$ 代表正在考虑第 $m$ 个约数。

首先从 $k, n, 0$ 开始。

终止条件：$d = 0$。

然后判断剩余的约数能否被取走。
因为在前面排了序，所以接下来的一定是比后面更小的，如果前面小的都除不尽的话就说明大的也没戏。

CODE

int l = d, u = 1;
fors(i, m, i<a.size() && l--, 1) if ((u*=a[i]) > p) return 0;

接下来挨个找可以被整除的约数。
$u$ 代表的是接下来 $d$ 个约数的积。

CODE

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.