c++ - 为什么错误的答案 Uva : Factovisors

Question

对于UVa Online Judge 上的问题10139 - Factovisorsn ，给出了 2 个数字和m，我们需要检查是否m除以n!。

我使用算法：

生成素数直到 const 数
取其m质数因子
对于m的因子中的每个素数，计算getpower函数n并比较它们

我测试了不同的案例，它也给了我错误的答案，有什么建议吗？

这是我的代码：

bool Factovisor (int n, int m) {

/* Special Cases */ 

    if(n==0 && m!=1 ) 
        return false;
    else if(n==0&&m==1) 
        return true;
    else if(m==0) 
        return false;
    else if(m==n||m==1) 
        return true;
    else if (n >= m)
        return true;
    else {

        vector <factores> factores_in_m; 
        int index = 0;
        int k=m;
/* first I generate all primes in primes vector */

        for (int i = 0; i < primes.size(); i++) {
            if (primes[i] > k) {
                break;

            } else {
/* factores is struct contain the prime and count*/

                factores f = {primes[i], 0};
                while (k % primes[i] == 0) {
                    f.count += 1;
                    k = k / primes[i];
                }

                if (f.count) {
                    factores_in_m.push_back(f);
                }
            }
        }

        if (k > 1) { 
            if (n < k) {
                return false;
            } else {
                factores f;
                f.prime= k;
                f.count =1;
                factores_in_m.push_back(f);
            }
        }

        for (int i = 0; i < factores_in_m.size(); i++) {
            if (factores_in_m[i].count - get_powers(n, factores_in_m[i].prime) > 0) {
                return false;
            }
        }
        return true;
    }
}

int get_powers (int n, int p) {
    int result = 0, power = p;
    while (power <= n) { 
        result += n / power;
        power =power* p;
    }
    return result;
}

bool isPrime (int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void get_prime () {
    for (int i = 2; i < maxn0; i++) {
        if (isPrime(i)) {
            primes.push_back(i);
        }
    }
}

score 3 · Accepted Answer

也许您的主要一代有问题，但您的get_powers实现肯定容易int溢出。

int get_powers (int n, int p) {
    int result = 0, power = p;
    while (power <= n) { 
        result += n / power;
        power =power* p;
    }
    return result;
}

如果int它通常是 32 位宽的类型，那么对于大于 46341 的素数，计算power = power * p;在第一次完成时会溢出。例如，这可能会导致错误的结果

get_powers(10000000, 131071)

如果溢出行为是环绕模 2 ³²，则返回 52，但正确的结果将是 76。现在，由于m小于 2 ³¹，因此这个特定的不会受到伤害，因为m不能被 131071²整除。但在环绕行为下，

get_powers(1000000, 699733) = -2192

是负数，因此例如，您会错误地得出结论n = 1000000不能被整除。m = 2*699733n!m

为避免可能的溢出，仅除以p,

int get_powers(int n, int p) {
    int result = 0;
    n /= p;
    do {
        result += n;
        n /= p;
    }while(n > 0);
    return result;
}

从评论：

我编辑添加了我的函数以获取素数，直到常数“maxn0” – userG 2 小时前

你为 maxn0 选择了什么值？– Daniel Fischer 2 小时前

maxn0 = 10000

这个值太小了。

对于 10000 的素数，您只能保证正确分解不超过 10 ⁸的数字（好吧，因为下一个素数是 10007，数字小于10007² = 100140049），但限制为 2 ³¹，这要大得多。

每当一个数字m给出两个（不一定是不同的）大于 10000 的素因数时，您将无法正确分解它，这通常会导致错误的答案。

您需要所有素数 ≤ √(2 ³¹ -1)，即所有素数< 46340才能获得所有可容许的正确分解m。

score 1 · Accepted Answer

编辑：由于对问题的误解而导致错误答案。

9除7！但是您的算法会回答错误，因为get_powers(7, 3) == 03 是 9 的因数。

错误的不是你的实现，而是你的算法。

c++ - 为什么错误的答案 Uva : Factovisors

2 回答 2

Related

Reference