5

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

Задано натуральное число 0<K<2^16 и число 1<N<11. Определить максимальную степень C числа N, чтобы число N^C было делителем числа K!

2
  • "NC" -- значит N в степени C? 14 дек 2012 в 18:33
  • Да, извиняюсь, сейчас исправлю
    – RubyNub
    14 дек 2012 в 19:53

8 ответов 8

10

Если вы просите алгоритм, то получайте алгоритм :).

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

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

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

  3. Ну и теперь, достаточно подобрать(или посчитать) максимальное C так, чтобы степени простых множителей у N были не больше, чем у К!.
5
  • Собственно мой алгоритм это и делает.
    – KoVadim
    14 дек 2012 в 19:26
  • 2
    @KoVadim, ок, мне просто было страшно читать :) 14 дек 2012 в 19:40
  • У Вашего алгоритма только одна проблема. В задаче автора ничего не сказано о a и b, а Вы не вводите их объяснений. Поэтому первых пункт невозможно выполнить. А это уже не алгоритм.
    – KoVadim
    15 дек 2012 в 8:59
  • 1
    @KoVadim: не будьте формалистом. Ясно же, что в ответе имелось в виду "для произвольных положительных a и b". Тем более, эта фраза не часть алгоритма, а объяснение его правильности.
    – VladD
    15 дек 2012 в 12:35
  • ага, там уже исправили:). В этом алгоритме не рассматривается, как именно быстро и качественно разложить на множители.
    – KoVadim
    15 дек 2012 в 12:38
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 <iostream>
// это тип на 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. Но это уже домашнее задание. Замерял время - работает очень быстро - доли секунды.

12
  • Что-то больно сложно. #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int k, n, c, i; k = atoi(argv[1]); n = atoi(argv[2]); if (n == 1) printf("На единицу я могу делить очень долго, Вы устанете ждать\n"); else { for(c =0, i = 2; i <= k; i++) { int i1 = i; while (i1 % n == 0) { c++; i1 /= n; } } printf("%d! делится на %d %d раз\n", k, n, c); } return 0; }
    – alexlz
    14 дек 2012 в 19:21
  • @alexlz если бы всё было так просто... factorial(18)/6**8 == 3811808000.0 Ваша программа выводит 3. Ошибочка... 14 дек 2012 в 19:30
  • да и к чему такие большие цифры. уже при k = 6 n = 4 выдает 1. Хотя 6! = 720 = 2*2 * 2*2 * 3*3 * 5. Что бы эта программа заработала, она должна учитывать те i1, которые меньше 11, но число не делиться.
    – KoVadim
    14 дек 2012 в 19:34
  • 1
    Увы, был неправ.
    – alexlz
    14 дек 2012 в 19:36
  • @alexlz - Ваша программа написана на С, а не на плюсах.
    – KoVadim
    14 дек 2012 в 19:43
2

Несложная задачка по теории чисел. Считаем число 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 можно сделать рекурсивно вычисляемым.
Но это другая история.

1

Понятно, что 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 и теперь сильно сомневаюсь в правильности своего алгоритма.

Оставлю пока для критики.


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

А может просто удалить, чтобы никому голову не забивать?

3
  • Я вижу в алгоритме идею, но она очень затуманена. Если я правильно ее понимаю, то работать не будет.
    – KoVadim
    14 дек 2012 в 19:16
  • 216! = 10020433703146107793945530580431357292843659510789309313207995121373860606589847385945865560132189286729581631646771816292076748699480508994205891351735346846175840399711009180476263461053865430706302603038547814701315906976472960428480208333486967446000761264392925098038248675260009865190052218097905890960111329206361438189114736515107632937864524405156085760000000000000000000000000000000000000000000000000000. Это большое число? 14 дек 2012 в 19:21
  • @KoVadim, теперь я и сам вижу, что не будет работать. У меня совершенно не учитывается вклад предшествующих K сомножителей, которые тоже делятся на N**C.
    – avp
    14 дек 2012 в 19:38
1

Сделано. Написано правда на Java, но работает на ура. Даже для любых N. Идея алгоритма точно такая же, как у Алексея Лобанова.

public class Task {
public static int compute(int k, int n) {
    List<int[]> 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<int[]> factorize(int n) {
    List<int[]> result = new ArrayList<int[]>();
    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<int[]> 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) 
}

}

1
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;
}
1
  • 2
    А это теперь так модно - публиковать свой ответ от имени сообщества? @AndrewSmith а в плюсах нет операции ^^
    – KoVadim
    14 дек 2012 в 19:46
0

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

#include <stdio.h>
#include <stdlib.h>

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 <sizeof simple/sizeof(int); i++)
            if(nfact[i]) {
                res[i] /= nfact[i];    // делим на количество таких множителей в n (для 8 -- nfact[0] == 3,  и число 2**10 делится на 8 10/3=3 раза.
                // минимальное ненулевое. 
                // количество уже нормировано по кол. множителей в n
                // то, что свыше минимума, ещё одного n не образует.
                if(res[i] && (!c || c > res[i])) c = res[i];
            }
        printf("%d! делится на %d %d раз\n", k, n, c);
    }
    return 0;
}

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

upd: немного подправил.

upd: добавил объяснения.

6
  • учитывая новые условия - не работает. ну как минимум при очень больших числа.
    – KoVadim
    14 дек 2012 в 20:11
  • Можно простыми словами коротко описать, если не составит труда конечно?
    – RubyNub
    14 дек 2012 в 20:11
  • По идее, на числах из условия, должно работать. Если N больше 11, то лажа... 14 дек 2012 в 20:18
  • Дополнил ответ. Если n > 11, то нужно разложить его на простые множители. Длины массивов будут другими. Ну и не будет надобности держать неиспользуемые простые числа.
    – alexlz
    14 дек 2012 в 20:29
  • я специально тестил при k > 50000. выдает заведомо неверный результат. Более того, меняя k, имеем один и тот же результат.
    – KoVadim
    14 дек 2012 в 20:46
0

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

#include <tuple>
#include <vector>
#include <algorithm>
#include <iostream>

using Factor = std::tuple<unsigned, unsigned, unsigned>;
using Factors = std::vector<Factor>;

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.