[题解] 3D Sodoku

本来想放到公开赛里的，但是被某低配版 AI 速通了。

简化题意：给定 $n$，是否存在 $a,b,c,d,e>1$，使得 $n=abc=de$，且 $\{a,b,c\}\cap\{d,e\}=\varnothing$。集合均可重。

显然 $\Omega(n)$ 需要大于等于 $3$。

进一步的，如果 $\Omega(n)=3$，设 $n=p_1p_2p_3$，无论如何，$d,e$ 一定会与 $p_1,p_2,p_3$ 中一个重复，那么设 $n=p_1p_2p_3p_4$。我们来看看什么样的可行什么样的不可行。为了方便我们不妨设 $p_1\le p_2\le p_3\le p_4$。

首先有一个可以发现的拆分是 $a=p_1,b=p_2,c=p_3p_4,d=p_1p_3,e=p_2p_4$。

然后考虑什么东西可能相等（以下 $p\le q\le r$）。

$p_3p_4=p_1p_3$，即 $p_1=p_4$，即 $p^4$ 型，包含在了下一种情况。

$p_3p_4=p_2p_4$，即 $p_2=p_3$，也即 $pq^2r$ 型。

那我们又可以发现一个拆分 $a=pq,b=q,c=r,d=pr,e=q^2$。

$pq=pr,pq=q^2,r=q^2$ 是可能出现的，第一种情况即 $fg^3$ 型，第二种情况即 $xy^4(x\le y)$ 型。

看第一种情况。

$a=fg,b=g,c=g,d=f,e=g^3$ 是一种可能的拆分。

$fg=g^3$ 是可能出现的，即 $p^5$ 型。

$f=g$ 是可能出现的，即 $p^4$ 型。

看第二种情况。

$a=x,b=y^2,c=y^2,d=xy,e=y^3$ 是一种可能的拆分。

$y^2=xy$ 是可能出现的，即 $p^5$ 型。

那么我们在 $\Omega(n)\ge4$ 的数中，只有 $p^4$ 型和 $p^5$ 型没有解决。

考虑证明这两个是不行的。

先考虑 $p^4$，$\{a,b,c\}$ 可能的只有 $\{p,p,p^2\}$，$\{d,e\}$ 若不含有 $p$ 和 $p^2$，$de$ 至少有 $p^6>p^4$。

再考虑 $p^5$，$\{a,b,c\}$ 可能的只有 $\{p,p^2,p^2\}$ 和 $\{p,p,p^3\}$，第一种情况，$\{d,e\}$ 若不含有 $p$ 和 $p^2$，$de$ 至少有 $p^6>p^5$，第二种情况，$\{d,e\}$ 若不含有 $p$ 和 $p^3$，$de$ 至少有 $p^4<p^5$，第二小的 $de$ 是 $p^6>p^5$，因此不成立。

结论：当且仅当 $n$ 有 $4$ 个可相同质因数且不型如 $p^4$ 与 $p^5$ 时，有符合题意的分解。