[题解] 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_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$ 时，有符合题意的分解。