“酷小子”CodeChef挑战

Question

我在试着解决一个关于CodeChef的问题。我的代码在我的IDE (这里的Visual)中非常好，但是当我在CodeChef上提交我的代码时，它说“超过了时间限制”。

代码的作用：

• 输入测试用例的T数，每个测试用例有一个输入N
• 设A和B是从1，2，3.N中随机选取的两个数
• 输出每个测试用例最大公因子A和B等于B的概率。

int _tmain(int argc, _TCHAR* argv[])
{
    int T;
    cin>>T;
    int tests[1000];
    for(int k=0;k<T;k++) //  Take the test cases as input
        cin>>tests[k];




    for(int i=0;i<T;i++)   // the main loop that runs T times
    {
        int N=tests[i];

        int result=2*N-1;   //  the numerator of the result

        int square=N*N;   //  the denominator of the result

        for(int j=2;j<=(N/2);j++)   
        {
            result=result+(N/j)-1;
        }

        for(int w=2;w<=result;w++)  //  Loop to convert fraction into irreducible form
        {
            if(result%w==0 && square%w==0)
            {
                result=result/w;
                square=square/w;
                w--;
            }
        }

        cout<<result<<"/"<<square<<endl;
    }
    return 0;
}

如何优化我的这段代码，使其在指定的时限内编译？任何可能的优化？

Answer 1

• _tmain()和_TCHAR都是微软特有的，是不可移植的.只需让他们分别main()和char。
• 模板语句中常用的名称是T。即使给出了解释，也可能会使其他人感到困惑，特别是当您最终在某个地方添加模板时。您可以将它重命名为testCases或类似的东西。
• 为了提高可读性，在操作数之间有更多的空格是很好的。例如，这个: for(int k=0;k
• 您有一些不太有用的注释: //将测试用例作为输入--根据它所做的，这一点已经很明显了。//运行T次的主循环--基于循环语句--这也是显而易见的。int结果=2*N1；//结果int square=N*N的分子；//结果的分母，尽管不一定是无用的注释，但它们表明可以给这些变量更准确的名称。它还将有助于赋予使用这些变量的最后一个cout语句更多的意义。

Answer 2

算法

这将是值得解释一下你做了些什么。无论如何，以下是一些数学事实：

• 对于A，B正整数，GCD(A，B) == B等价于A是B的倍数。
• 对于1，N中的A，B，我们有N^2对(A，B)
• 对于1，N中的B，我们有地板(N/B)元素A，使得A在1，N中是B的倍数。特别是，如果B是1，我们就有N个元素。
• 要减少分数，可以使用欧几里得算法。

最后一个可能对你有用的事实。

测试与代码组织

在任何情况下，如果您想优化代码，我建议您编写一些测试用例(具有巨大的值，这样您就可以看到瓶颈所在)。为了编写这些测试，您可能会发现编写具有单个响应性的小函数更为方便。

在这样做时，您可能会意识到，您实际上不需要将输入存储在数组中，只需要在之后遍历数组。你也许可以写这样的东西：

typedef frac // TODO
int get_gcd(int a, int b); // TODO
frac get_proba_as_irreducible(int N); // TODO
void print_proba(frac); // TODO

int _tmain(int argc, _TCHAR* argv[])
{
    int T;
    cin>>T;
    for(int k=0;k<T;k++)
    {
        int N;
        cin >> N;
        print_proba(get_proba_as_irreducible(N));
    }
    return 0;
}