Максимальная степень множителя у факториала

#cpp #алгоритм #битовые_операции

Приветствую, помогите, пожалуйста, с алгоритмом такой задачи:

Задано  натуральное число 0

Ответы
Ответ 1

Если вы просите алгоритм, то получайте алгоритм :).
Заметим, что a ⋮ b равнозначно следующему: степень любого простого множителя в a
не меньше степени соответственного множителя в b. Ну а теперь, переходим к задаче:


Раскладываем N на простые множители в
    какой-то степени(оно небольшое, и
    это можно сделать быстро).


Далее, определяем степени этих множителей в K!. Их можно посчитать так: каждое p-е
число делится на p, каждое p-е из выбранных тоже делится на p и т.д.

Ну и теперь, достаточно подобрать(или посчитать) максимальное C так, чтобы степени
простых множителей у N были не больше, чем у К!.


Ответ 2

1) подготовка. Нам нужен будет массив делителей первых 216 чисел. Его можно будет
хоть ручками заготовить. Он вот такого виде (1) (2) (3) (2,2) (5) (2,3) (7) (2, 2,
2) (3,3) (2,5) ... и так далее до (2,2,2,3,3,3). Это по факту - двумерный массив 216*7
(у чисел до 216 более 7 делителей не будет. Почему? легко доказать, чем меньше делитель,
тем больше их "влезет" в одно и тоже число. Минимальный делитель - 2. 2 в 8 это уже
256). Но, как будет показано ниже, нам нужно будет на самом деле массив 216 * 4, так
как делители больше 7 нам уже не интересны. (и выглядеть он будет так ((0 0 0 0) (1
0 0 0) (0 1 0 0) (2 0 0 0) (0 0 1 0) (1 1 0 0) (0 0 0 1) (3 0 0 0) (0 2 0 0) (1 0 1
0)...) (в скобках указанно кол-во делителей 2 3 5 и 7).
2) Теперь нам нужно пройти по указанному выше массиву от 1 до К и посчитать, сколько
раз встретились 2 3 5 и 7.

3). А вот теперь пришло время расчета. Пусть K было 216. Получим такую таблицу
2 212
   3 106
   5  52
   7  34
И нужно рассчитать для С = 2. Понятно, что только двойки и принимают участие. ответ
- 212. Пусть нужно рассчитать для 4. Так как 4 = 2*2, то степень в два раза меньше.
Поэтому ответ 106.  для 5 - 52. C 8 чуть сложнее. Для нее нужны 3 двойки. 212 нацело
на 3 не делиться, поэтому берем только целую часть.
N C
2 212
3 106
4 106
5 52
6 106
7 34
8 70
9 53
10 52

upd
В связи с тем, что выяснились новые обстоятельства, меняем.
Придумал приближенный способ. Понятно, что если вычислить логарифм K!, то разделив
его на логарифм N, сразу бы получили С. И оказывается, такая формула есть.
Так как числа стали большими, я сделал чуточку хитрый код.
#include 
// это тип на 4 элемента
typedef int prime[4];

// эта функция подсчитывает кол-во делителей 2 3 5 7 для заданного числа.
// да, тут копипаста, но так быстрее.
void getP(int x, prime& r)
{
    while (x > 0 && x % 2 == 0) {
        x /= 2;
        r[0]++;
    }

    while (x > 0 && x % 3 == 0) {
        x /= 3;
        r[1]++;
    }
    while (x > 0 && x % 5 == 0) {
        x /= 5;
        r[2]++;
    }
    while (x > 0 && x % 7 == 0) {
        x /= 7;
        r[3]++;
    }
}

int main()
{
    int n, k;
    int c = 0;
    std::cout << "Enter n:";
    std::cin >> n;
    std::cout << std::endl << "Enter k:";
    std::cin >> k;
    std::cout << std::endl;
    prime q = {0,0,0,0};
    for (int i = 2; i <= k; i++) {
        getP(i, q);
    }
// выведем делители, для контроля
    std::cout << "2: " << q[0] << ", 3: " << q[1] << ", 5: " << q[2] << ", 7: " <<
q[3] << std::endl;
// каждый случай обработаем отдельно
// можно было бы разложить на множители...
    switch (n) {
    case 2:
          c = q[0];
          break;
    case 3:
          c = q[1];
          break;
    case 4:
          c = q[0] / 2;
          break;
    case 5:
          c = q[2];
          break;
    case 6:
          c = q[0] < q[1]?q[0]:q[1];
          break;
    case 7:
          c = q[2];
          break;
    case 8:
          c = q[0] / 3;
          break;
    case 9:
          c = q[1] / 2;
          break;
    case 10:
          c = q[0] < q[2]? q[0]:q[2];
          break;
    default:
          c = 0;
          std::cout << " n = " << n << ", but have to be in [2..10]" << std::endl; 
          break;
    }
    std::cout << "C = " << c << std::endl;
    return 0;
}

если все таки захочется сделать через разложение.
нужно поэлементно разделить один массив на другой (при этом считать, что 0/0 равно
0) и найти в этом массиве минимальное число, больше 0. Но это уже домашнее задание.
Замерял время - работает очень быстро - доли секунды.


Ответ 3

Несложная задачка по теории чисел. Считаем число p простым и вводим обозначения    

[a] - для целой части числа a и
ord(a,p) - для показателя простого числа p в каноническом разложении числа a.    

Из теории чисел (разложение факториала) известно, что    

ord(K!,p) = [K/p] + [K/p^2] + ... + [K/p^n]


При этом n=[log(p)K], а практически  

n= [lg(K+0.5) / lg p]


В нашем случае (N=2...10) 

N=p(0)^r(0,N)*p(1)^r(1,N)*p(2)*r(2,N)*p(3)^r(3,N),    


где p={2,3,5,7}, а массив r(i,N) можно ввести вручную.

Ответ:

С=min (i, r(i,N)>0) {[K!#p(i) / r(i,N)]}.


P.S. В случае N>10 массив r можно сделать рекурсивно вычисляемым.
Но это другая история.


Ответ 4

Понятно, что 216! это очень большое число. Видимо вычислять его не стоит и пытаться,
а надо представить в виде массива сомножителей. 
Если "в лоб", то
long bigNum[214];

и заполнить числами 2,3,4,...216 (очевидно далее не сложно обобщить до K).
Далее для каждого элемента массива считаем x = N**C, перебирая C от 2 (1 ?) и пока
N**C меньше bigNum[i]. Если x = N**C равно bigNum[i], то
if (x > max) {
   maxC = C;
   max = x;
}

Собственно, видимо все. maxC это ответ.
Кажется так.

Посмотрел ответ @KoVadim и теперь сильно сомневаюсь в правильности своего алгоритма.
Оставлю пока для критики.

Алгоритм неправильный. Можно оставить только в качестве примера ошибочных (и неполных)
рассуждений.
А может просто удалить, чтобы никому голову не забивать?


Ответ 5

Сделано. Написано правда на Java, но работает на ура. Даже для любых N.
Идея алгоритма точно такая же, как у Алексея Лобанова.
public class Task {
public static int compute(int k, int n) {
    List primes = factorize(n);
    int[] powers = countPowers(k, primes);
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < powers.length; ++i) {
        int c = powers[i] / primes.get(i)[1];
        if (c < min)
            min = c;
    }
    return min;
}

private static List factorize(int n) {
    List result = new ArrayList();
    int exp = 0, diw;
    for (; (n & 1) == 0; n >>= 1)
        ++exp;
    if (exp > 0)
        result.add(new int[] { 2, exp });
    for (diw = 3, exp = 0; diw * diw <= n; diw += 2, exp = 0) {
        for (; n % diw == 0; n /= diw)
            ++exp;
        if (exp > 0)
            result.add(new int[] { diw, exp });
    }
    if (n > 1)
        result.add(new int[] { n, 1 });
    return result;
}

private static int[] countPowers(int k, List primes) {
    int[] result = new int[primes.size()];
    for (int i = 0; i < result.length; ++i) {
        int prime = primes.get(i)[0];
        for (int power = prime; power <= k; power *= prime)
            result[i] += k / power;
    }
    return result;
}

public static void main(String[] args) {
    System.out.println(compute(3, 3)); // 1
    System.out.println(compute(6, 3)); // 2
    System.out.println(compute(6, 4)); // 2
    System.out.println(compute(37 * 37, 37)); // 38
    System.out.println(compute(70, 5 * 5 * 11)); // 6
    System.out.println(compute(25, 180 /* 2*2*3*3*5 */)); // 5 (25! не делится на 3^12) 
}

}


Ответ 6

uint maxDividerPower(uint k, uint n)
{   
//находим ближайшую степень делителя
uint power = floor( log10(k) / log10(n) );

//перебираем все степени от максимальной до 0   
do{
    if ( (k % n^^power) == 0 ) break;
    --power;
}while( power>0 );

return power;
}


Ответ 7

Вроде исправил.
#include 
#include 

int main(int argc, char *argv[]) 
{ 
    int k, n, i;
    int simple[] = {2, 3, 5, 7, 11};
    int nfact[] = {0, 0, 0, 0, 0};
    int res[] = {0, 0, 0, 0, 0};
    k = atoi(argv[1]);
    n = atoi(argv[2]);
    if (n == 1) printf("На единицу я могу делить очень долго, Вы устанете ждать\n");
    else {
        int c, j, n1 = n;
        // находим простые множители n (и их количество). Результат -- в nfact
        for(i = 0; i < sizeof simple/sizeof(int); i++) 
            while(n1 % simple[i] == 0) {
                n1 /= simple[i];
                nfact[i]++;
            }
        for(j = 2; j<= k; j++) {
            int j1 = j;
            for(i=0; i < sizeof simple/sizeof(int); i++)
                if(nfact[i])    // если n имеет такой множитель. Если нет -- простой
множитель нам не интересен
                    while(j1 % simple[i] == 0) {
                        j1 /= simple[i];
                        // общее количество множителей simple[i] в факториале.
                        res[i]++;
                    }
        }
        for(c = 0, i = 0; i  res[i])) c = res[i];
            }
        printf("%d! делится на %d %d раз\n", k, n, c);
    }
    return 0;
}

Плюсы и расширение на случай n > 11 остаются в качестве домашнего задания.
upd: немного подправил.
upd: добавил объяснения.


Ответ 8

Классическая задача на выполнение факторизации и на формулу Лежандра. Решение в разных
степенях готовности и полноты уже приведено. Приведу и свой С++ вариант (без ограничения
на N)

#include 
#include 
#include 
#include 

using Factor = std::tuple;
using Factors = std::vector;

Factors factorize(unsigned n)
{
  Factors factors;    

  for (unsigned d = 2; d <= n; ++d)
    if (n % d == 0)
    {
      factors.emplace_back(0, d, 0);
      for (; n % d == 0; n /= d)
        ++std::get<2>(factors.back());
    }

  return factors;
}

void legendre(unsigned k, Factors &factors)
{
  for (Factor &factor : factors)
  {
    for (unsigned f = std::get<1>(factor); k > f; f *= std::get<1>(factor))
      std::get<0>(factor) += k / f;
    std::get<0>(factor) /= std::get<2>(factor);
  }
}

int main() 
{
  unsigned k, n;
  std::cin >> k >> n;

  Factors factors = factorize(n);
  legendre(k, factors);

  auto it = std::min_element(factors.begin(), factors.end());
  std::cout << std::get<0>(*it) << std::endl;
}