-1

数Mよりも小さい数Nの互いに素な数を見つけるための関数を書きたいのですが、Mは

そのために、私はオイラーのトーティエント関数を変更するこのリンクを参照しました

次の再帰コードを作成しました。

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、配列内の素数のいずれかで割り切れる数を超えない数を返すことを意図しているようです。factorsstart

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]);
}

明らかに、プライムが1つしかないp場合、カウントはm / pです。ここまでは順調ですね。さて、他の部分の考え方は、それを超えない数の数は、または後の素数の1つで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

これは漸近的に正しいだけです。たとえば、3つの素数[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、3つの素数のいずれでも割り切れない6つの数が1, 7, 11, 13, 17, 19あるため、3つのいずれかの倍数であるのは14だけです。

後の素数の倍数と後の素数のいずれかを説明する正しい方法は、後の素数の倍数であり、後の素数の少なくとも1つである場合、は倍数であるため、pを超えない後の素数の倍数を数えることです。を超えない後の素数の1つの。m/pkpk/pm/p

したがって、関数の修正は、括弧を移動するだけで構成されます（まあ、2つあるので、たくさんあります）。

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 に答える