c++ - ACM国际大学编程竞赛亚洲区域D亨利

给定分数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();
}

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

最佳答案

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

关于c++ - ACM国际大学编程竞赛亚洲区域D亨利，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39352780/