P1482 Cantor表（升级版）

P1482 Cantor表（升级版）

提交58.99k

通过24.12k

时间限制1.00s

内存限制125.00MB

提交答案加入题单

做题计划（首页）

个人题单

团队题单

保存

题目提供者情到深处人孤独

难度入门

历史分数无

 提交记录  查看题解

标签

洛谷原创

 查看算法标签

进入讨论版

相关讨论

 查看讨论

推荐题目

 查看推荐

 洛谷推荐关闭

 复制Markdown  展开

题目描述

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

1/11/21/31/41/5⋯2/12/22/32/4⋯3/13/23/3⋯4/14/2⋯5/1⋯1/12/13/14/15/1​1/22/23/24/2⋯​1/32/33/3⋯​1/42/4⋯​1/5⋯⋯

这次与 NOIp1999 第一题不同的是：这次需输入两个分数（不一定是最简分数），算出这两个分数的积（注意需要约分至最简分数），输出积在原表的第几列第几行（若积形如 aa（即结果为整数）或者 1/a1/a，则看作表内的 a/1a/1 或 1/a1/a 结算）。

输入格式

共两行。每行输入一个分数（不一定是最简分数）。

输出格式

两个整数，表示输入的两个分数的积在表中的第几列第几行。

输入输出样例

输入 #1复制

4/5
5/4

输出 #1复制

1 1

说明/提示

数据范围

对于全部数据，两个分数的分母和分子均小于 104104。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace Practise_10._30_Cantor_plus
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Cantor();
            Console.ReadKey();

        }
        static void Cantor()
        {
            {
                string input = Console.ReadLine(); // 读入一行输入
                string[] parts = input.Split('/'); // 按 '/' 分割

                // 解析输入
                int a = int.Parse(parts[0]);//4
                int b = int.Parse(parts[1]);//5
                int c = int.Parse(parts[2]);//5
                int d = int.Parse(parts[3]);//4

                a *= c; // 乘一下
                b *= d; // 乘一下

                int t = GCD(a, b); // 求最大公约数
                a /= t; // 约分
                b /= t; // 约分

                Console.WriteLine($"{b} {a}"); // 输出


            }
        }
        static int GCD(int a, int b) // 辗转相除法求最大公约数
        {
            if (b == 0) return a; // 如果 b = 0，a 是最大公约数
            return GCD(b, a % b); // 否则继续
        }
    }
}

GCD:

• 定义一个静态方法 GCD，使用辗转相除法（欧几里得算法）计算两个整数的最大公约数。如果 b 为 0，则返回 a；否则递归调用 GCD 方法。