0

Interviewstreet には、UnfriendlyNumbers という問題があります。問題は次のようになります -

1 つの友好的な番号と N の非友好的な番号があります。友好的な数を正確に分割し、非友好的な数を分割しない数がいくつあるかを見つけたいと考えています。サンプル入力: 8 16 2 5 7 4 3 8 3 18 サンプル出力: 1

私が想像できるすべてのテストケースは正しく実行されますが、何らかの理由で、Web サイトは一連のテストケースに対して正しくないと見なします。コード/ロジックにエラーはありますか?

void get_factors(unsigned long n, vector<unsigned long> &factors)
{
    unsigned long sqrt = pow(n, 0.5);
    for (unsigned long i = 1; i < sqrt; i++) {
        if (n%i == 0) {
            factors.push_back(i);
            factors.push_back(n/i);
        }
    }
    if (n%sqrt == 0) {
        factors.push_back(sqrt);
    }
}


int
main(int argc, char *argv[])
{
    unsigned int n; 
    unsigned long k, j;
    cin >> n >> k;

    if (n == 0 || k == 0) {
        cout << 0 << endl;
        return 0;
    }

    set<unsigned long> unfriendly;
    for (int i = 0; i < n; i++) {
        cin >> j;
        unfriendly.insert(j);
    }

    vector<unsigned long> factors;
    get_factors(k, factors);

    unsigned int count = factors.size();
    for (int i = 0; i < factors.size(); i++) {
        for (set<unsigned long>::iterator it = unfriendly.lower_bound(factors[i]); 
             it !=  unfriendly.end();
             it++)
        {
            if (*it % factors[i] == 0) {
                count--;
                break;
            }
        }
    }
    cout << count;
}
4

2 に答える 2

4

あなたget_factorsは間違っています。30 や 35 などの数値では、一部の除数が省略されます。

sqrtは平方根を超えない最大の整数ですが、n == sqrt*(sqrt+1)またはの場合はrespn == sqrt*(sqrt+2)を記録しません。除数として。sqrt+1sqrt+2

また、その可能性もある

unsigned long sqrt = pow(n, 0.5);

nが十分に大きい場合、誤った結果が生じる可能性があるため、調整することをお勧めします

while(sqrt > n/sqrt) --sqrt;
while(sqrt+1 <= n/(sqrt+1)) ++sqrt;

また、unsigned long安全に使用するには、十分な大きさではない可能性がありますunsigned long long。

それとは別に、失敗する可能性があるのは、数字のいずれかが0の場合だけです。

    for (set<unsigned long>::iterator it = unfriendly.lower_bound(factors[i]); 
         it !=  unfriendly.end();
         it++)

友好的でない番号が 0 の場合は失敗します。友好的な番号が 0 の場合、すべての賭けはオフです (非友好的な番号が 0 の場合、答えは 0 であり、それ以外の場合は無限大です)。

于 2012-04-18T20:54:19.430 に答える
0

GCDを使用して、非友好的な数と友好的な数Kの間の最大公約数を取得します。オン）

次に、O（sqrt（K））でKの約数を取得します。

cmn_divとkのdivをループして、O（N * sqrt（K））で答えを取得します。

于 2013-01-16T12:55:09.600 に答える