c++ - ACM 国际大学生程序设计大赛亚洲赛区 D Henry

Question

给定分数 a / b , 其中a和 b是正整数并且a < b , 选择最大单位分数 1 / x_1这样 1 / x_1 <= a / b .然后减去1 / x_1来自 a / b , 并对余数重复该过程:选择最大单位分数 1 / x_2这样 1 / x_2 <= (a / b) - (1 / x_1) .再次重复，直到没有剩余。此过程将产生一系列单位分数 1 / x_1, 1 / x_2, 1 / x_3, ...总和为给定分数 a / b .对于任何输入分数 a / b，此过程总是终止具有有限数量的不同单位分数。编写一个程序，打印出结果系列中最后一个分数的分母。

示例:

5/7 = 1/2 + 1/5 + 1/70

示例输入:

3 
4 23
5 7
8 11

输出:

138
70
4070

代码:

我的代码是针对 C++ 语言的

#include <iostream>
#include <fstream>
using namespace std;
int testCase;
double a;
double son;
double mom;

int main()
{
    ifstream file("input.txt");
    file >> testCase;

    while (testCase--)
    {
        file >> son;
        file >> mom;

        while (son != 1)
        {
            a = (int)(mom / son) + 1;
            son = (son * a) - mom;
            mom = mom * a;
        }
        cout << mom << endl;
    }
    file.close();
}

我认为我的算法是正确的，但我的学校评分系统说它超出了运行时间限制。我不知道为什么。

Answer 1

您可能忘记了在每一步将 mom 和 son 除以它们的最大公约数 (GCD)。这可能会让某些示例永远运行或比预期运行更长时间。检查这是否是问题所在。另外，为什么要为 son 和 mom 使用 double 类型？分数的分子和分母应该是整数。如果它们可以是非常大的整数，只需使用 unsigned long int 或 size_t(c++ 中的同义词)。 double 数据类型没有 size_t 那么多的有效数字。