-1

我想编写一个函数来查找小于数字 M 的数字 N 的互质数，使得 M

为此，我参考了此链接修改 Euler Totient Function

我写了以下递归代码。

int f(int *factors, int start, int nf, int m) //nf=no. of factors, start=0, m=M
{
    if(start == nf-1) 
        return (m / factors[start]);

    return (m / factors[start]) + f(factors, (start + 1), nf, m) - ((f(factors, (start + 1), nf, m)) / factors[start]);
}

但是，我得到了错误的答案。

我想解决这个问题http://www.spoj.pl/problems/HNUMBERS/

我的代码为给定的测试用例给出了正确的答案，但对其他一些用例却失败了（因为他们向我展示了错误的答案）。

4

1 回答 1

1

您的函数f（您也许应该选择一个更具描述性的名称）似乎是为了返回不超过m可被数组中任何素数整除的数字计数factors，从索引start开始。

int f(int *factors, int start, int nf, int m) //nf=no. of factors, start=0, m=M
{
    if(start == nf-1) 
        return (m / factors[start]);

    return (m / factors[start]) + f(factors, (start + 1), nf, m)
              - ((f(factors, (start + 1), nf, m)) / factors[start]);
}

显然，只有一个素数p，计数是m / p。到目前为止，一切都很好。现在，另一部分的想法是，不超过m可被p或后来的素数之一整除的数的计数是

count_multiples_of_p + count_multiples_of_other - count_multiples_of_p_and_other

到目前为止是正确的。但是你的实现假设

count_multiples_of_p_and_other = count_multiples_of_other / p

这只是渐近正确的。例如考虑三个素数[2, 3, 5]和m = 20。

你的函数返回

F([2,3,5], 20) = 20/2 + F([3,5], 20) - F([3,5], 20)/2
    -- F([3,5], 20) = 20/3 + 20/5 - (20/5)/3 = 6 + 4 - 1 = 9
               = 10 + 9 - (9/2) = 10 + 9 - 4 = 15

但是如果你数一下，有六个数<= 20不能被三个素数中的任何一个整除1, 7, 11, 13, 17, 19，所以只有 14 是三个素数中的任何一个的倍数。

解释 的倍数p和任何后续素数的正确方法是计算任何不超过 的后续素数的倍数m/p，因为如果k是 的倍数p以及至少一个后续素数，那么k/p就是倍数不超过的后期素数之一m/p。

所以修复你的函数只需要移动一个括号（好吧，两个，因为你有这么多），

int f(int *factors, int start, int nf, int m) //nf=no. of factors, start=0, m=M
{
    if(start == nf-1) 
        return (m / factors[start]);

    return (m / factors[start]) + f(factors, (start + 1), nf, m)
              - ((f(factors, (start + 1), nf, m /* )) */ / factors[start]) ));
    //                                          ^^^^^^^^                   ^^
}

（并且您有几对多余的括号，您可以考虑删除其中的一些）。

于 2012-10-11T20:14:02.760 回答