0

在 interviewstreet 上有一个叫做 UnfriendlyNumbers 的问题。问题是这样的——

有1个友好号码和N个不友好号码。我们想找出有多少数字正好整除友好数字，但不整除任何不友好数字。样本输入：8 16 2 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;
}
4

2 回答 2

4

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

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

于 2012-04-18T20:54:19.430 回答
0

使用 GCD 获取不友好数和友好数 K 之间的公约数。上）

然后在 O(sqrt(K)) 中得到 K 的除数。

循环k的cmn_div和div，得到O(N*sqrt(K))的答案

于 2013-01-16T12:55:09.600 回答