问题：将$2^2 3^3 5^5 7^7$表示为两个互质的数$(a,b)$的乘积，满足$1 < a < b$，这样的方式有多少种？

你的尝试回顾 #

你当时的思路方向是对的——互质的两个数不能共享质因数，所以必须把4个质因数（2、3、5、7）的幂整体分给a或b。你分了三类：

• 类型i：a是单个质数的幂，b是剩下3个的乘积，共$C(4,1)=4$种
• 类型ii：a是任意2个质数的幂的乘积，b是剩下2个的，共$C(4,2)=6$种
• 类型iii：a是任意3个质数的幂的乘积，b是剩下1个的，共$C(4,3)=4$种
  加起来得到14种，但选项都≤8，显然哪里出问题了。

问题出在哪？ #

核心错误是没考虑$a < b$的限制，把有序对当成了无序对计数，而且部分分组其实是逆序的重复情况，还有些分组本身就不满足$a < b$。

举个例子：你算的类型i里，选$7^{7$给a，对应的b是$2}23³⁵5$，这时候a=823543，b=337500，明显a > b，不符合要求；而类型iii里选2、3、5给a，对应的b是$7^7$，这时候a=337500 < b=823543，是符合要求的，但你之前把类型iii的4种都算进去，其实大部分都不符合。

更关键的是：$(a,b)$和$(b,a)$是同一个组合的两种顺序，题目要的是$1 < a < b$的情况，所以不能重复计数。

正确解法 #

我们换个更清晰的思路：
对于$N=2²³35⁵⁷7$，它的质因数有4个不同的质数。要拆成互质的a和b，本质是把这4个质因数分成非空的两组（因为a和b都不能是1），每组的质因数的幂全部归到a或b。

1. 先算所有有序分法：每个质因数有2种选择（给a或给b），总共有$2^4=16$种。
2. 排除无效情况：
   • 所有质因数都给a：$a=N,b=1$，不符合要求
   • 所有质因数都给b：$a=1,b=N$，也不符合要求
     剩下$16-2=14$种有序对，这些都是$a≠1,b≠1,a≠b$的情况。
3. 转换为无序对：因为$(a,b)$和$(b,a)$是同一个组合，只是顺序相反，所以无序对的数量是$14÷2=7$种，这7种正好全部满足$1 < a < b$（因为N不是平方数，所以a不可能等于b）。

验证一下具体的7种情况 #

我们可以列出来确认：

• 单个质数幂作为a（且a < b）：$2^2$、$33$、$5^5$ → 3种
• 两个质数幂的乘积作为a（且a < b）：$2²³3$、$2²⁵5$、$3³⁵5$ → 3种
• 三个质数幂的乘积作为a（且a < b）：$2²³35^5$ → 1种
  加起来正好7种，完全符合计算结果。

所以你之前的错误就是没筛选掉a > b的情况，也没去除重复的有序对，现在修正后得到的7种就是正确答案啦。

备注：内容来源于stack exchange，提问作者math forever