Почему Неправильный ответ Ува: Factovisors

Question

Для задачи 10139 - Factovisors на UVa Online Judge, 2 номера n и m даны, и мы должны проверить, делится ли mn!.

Я использую алгоритм:

1. Генерация простых чисел до сопзЬ числа

2. Возьмите m и получить его штрихами фактор

3. Для каждого простого в m «s факторов, вычислить 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); 
     } 
    } 
} 

Answer 1

EDIT: неправильный ответ из-за misanderstanding вопроса.

9 делит 7! но ваш алгоритм ответит ложным, потому что get_powers(7, 3) == 0 и 3 является фактором 9.

Это не ваша реализация, это неправильно, но ваш алгоритм.

Answer 2

Возможно, ваше первое поколение неисправно, но, безусловно, ваша реализация 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) 

возвращает 52, если поведение переполнения оберточного типа по модулю 2 , но правильный результат будет 76. Теперь, поскольку m меньше, чем 2 , этот конкретный не повредит, так как m не может делиться на 131071². Но под оберточной поведение,

get_powers(1000000, 699733) = -2192 

отрицательна, поэтому для n = 1000000 и m = 2*699733, например, вы бы неверно полагать, что n! не делится на 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? - Даниэль Фишер 2 часа назад

maxn0 = 10000

Это значение слишком мало.

С простых чисел до 10000, вы только гарантированно правильно факторизовать числа, не превосходящие 10 (ну, так как следующий премьер является 10007, число меньше, чем 10007² = 100140049), но предел задается как 2 , что намного больше.

Когда число m задано с двумя (не обязательно отличными) основными факторами, превышающими 10000, вы не будете правильно его разлагать, и это обычно приводит к неправильному ответу.

Вам нужно все простые числа ≤ √ (2 -1), то есть все простые числа < 46340 для получения правильной факторизации всех допустимых m.