c++ - 不友好的数字c++

Question

interviewstreet 上有一个名为 UnfriendlyNumbers 的问题。问题是这样的-

有一个友好号码和N个不友好号码。我们想找出有多少数字恰好整除友好数字，但不整除任何不友好数字。示例输入:8 162 5 7 4 3 8 3 18示例输出:1

我能想象的所有测试用例都正确执行，但出于某种原因，网站认为它对一组测试用例不正确。你们看到代码/逻辑中有任何错误吗？

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

Answer 1

您的 get_factors 不正确。对于像 30 或 35 这样的数字，一些除数会被省略。

sqrt 是不超过平方根的最大整数，但是当 n == sqrt*(sqrt+1) 或者 n == sqrt*( sqrt+2)，你不记录 sqrt+1 resp。 sqrt+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，否则为无穷大)。