Cantor表问题解析与分数运算算法实现

1. Cantor表问题解析与升级版挑战

在数学和计算机科学的交叉领域，有一类问题因其独特的思维训练价值而备受青睐，Cantor表问题就是其中的典型代表。Georg Cantor通过这张神奇的表证明了有理数的可枚举性，这个证明不仅改变了数学的发展轨迹，也为算法设计提供了绝佳的练习素材。

1.1 经典Cantor表回顾

原始的Cantor表按照特定规律排列所有正有理数：

code复制1/1  1/2  1/3  1/4  1/5  ...
2/1  2/2  2/3  2/4  ...
3/1  3/2  3/3  ...
4/1  4/2  ...
5/1  ...
...

这个排列遵循"对角线枚举"原则：从左上角开始，沿对角线方向依次遍历。在NOIp1999的经典题目中，要求给定一个位置N，输出表中第N项的分数。这个版本考察的是对表结构的理解和位置计算能力。

1.2 升级版问题的核心变化

P1482题目对经典问题进行了三个关键升级：

1. 输入形式变化：从单一位置输入变为两个分数输入
2. 计算要求：需要对两个分数进行乘法运算并约分
3. 输出目标：不再是直接输出分数，而是找到结果分数在表中的行列位置

这种升级使得问题从单纯的位置计算转变为综合性的分数运算与位置映射问题，对参赛者的综合能力提出了更高要求。

关键提示：虽然题目允许输入非最简分数，但最终输出位置时必须使用最简形式，这是解题时容易忽略的重要细节。

2. 问题解法与算法设计

2.1 数学基础与解题思路

解决这个问题的关键在于理解三个数学概念：

1. 分数乘法：(a/b) × (c/d) = (a×c)/(b×d)
2. 约分运算：通过求分子分母的最大公约数(GCD)进行约简
3. 位置映射：约分后的分数m/n在表中的位置就是(n, m)

算法流程可以分解为：

1. 读取两个分数
2. 计算它们的乘积（分子相乘，分母相乘）
3. 对结果分数进行约分
4. 输出约分后分母作为列号，分子作为行号

2.2 核心代码实现解析

让我们深入分析提供的AC代码：

cpp复制#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int a1, b1, a2, b2;
    scanf("%d/%d%d/%d", &a1, &b1, &a2, &b2);
    int c1 = a1 * a2, c2 = b2 * b1;
    printf("%d %d\n", c2 / __gcd(c1, c2), c1 / __gcd(c1, c2