题意分析

1. 问题目标：

   • 给定两个正整数$A$和$B$，找到一个最小的质数集合$S$，使得$A$和$B$都可以表示为$S$中质数的幂的乘积。
   • 在由$S$定义的$|S|$维空间中，计算$A$和$B$对应的点之间的曼哈顿距离。

2. 关键点：

   • 最小空间维度$X$是$A$和$B$的所有质因数的并集的大小。
   • 距离$D$是$A$和$B$在每个质因数维度上的指数差的绝对值之和。

解题思路

1. 质因数分解：

   • 对$A$和$B$分别进行质因数分解，得到它们的质因数及其指数。
   • 例如，$168 = 2^3 \times 3^1 \times 7^1$，$882 = 2^1 \times 3^2 \times 7^2$。

2. 合并质因数集合：

   • 将$A$和$B$的质因数合并，得到唯一的质数集合$S$。
   • 对于$168$和$882$，$S = \{2, 3, 7\}$，因此$X = 3$。

3. 计算距离：

   • 对于$S$中的每个质数$p$，计算$A$和$B$在$p$的指数上的差的绝对值。
   • 将所有差的绝对值相加，得到曼哈顿距离$D$。
   • 例如：
     • $|3 - 1| = 2$（$p = 2$）
     • $|1 - 2| = 1$（$p = 3$）
     • $|1 - 2| = 1$（$p = 7$）
     • 距离$D = 2 + 1 + 1 = 4$。

4. 处理其他测试用例：

   • 对于$770$和$792$：
     • $770 = 2^1 \times 5^1 \times 7^1 \times 11^1$
     • $792 = 2^3 \times 3^2 \times 11^1$
     • $S = \{2, 3, 5, 7, 11\}$，$X = 5$。
     • 距离计算：
       • $|1 - 3| = 2$（$p = 2$）
       • $|0 - 2| = 2$（$p = 3$）
       • $|1 - 0| = 1$（$p = 5$）
       • $|1 - 0| = 1$（$p = 7$）
       • $|1 - 1| = 0$（$p = 11$）
       • 距离$D = 2 + 2 + 1 + 1 + 0 = 6$。

C++代码实现

#include <iostream>
#include <set>
using namespace std;
 
set<int>sum;
 
void get(int x){
	for (int i = 2; i*i <= x; i++){
		while (x%i == 0){
			sum.insert(i);
			x /= i;
		}
	}
	if (x > 1){
		sum.insert(x);
	}
}
 
int main()
{
	int n, m, kase = 1;
	while (cin >> n >> m&&n&&m){
		sum.clear();
		get(n);
		get(m);
		int ans = 0;
		set<int>::iterator it = sum.begin();
		for (; it != sum.end(); it++){
			int a = 0, b = 0;
			int temp = *it;
			while (n%temp == 0)a++, n /= temp;
			while (m%temp == 0)b++, m /= temp;
			ans += (a > b ? a - b : b - a);
		}
		cout << kase++ << ". " << sum.size() << ":" << ans << endl;
	}
}