1

Всем привет есть такая задача ,надо разложить число n на k множителей или вывести Impossible если это не возможно.Не знаю как можно решить .Можете помочь или подсказать алгоритм для решения этой задачи ?

4
  • Нужен хотя бы один способ или перечислить все возможные?
    – Harry
    15 апр 2017 в 16:00
  • Один способ нужно вывести 15 апр 2017 в 16:00
  • Книжки не пробовали читать? Навскидку - Д. Кнут.
    – andy.37
    15 апр 2017 в 16:03
  • 2
    На правах Капитана Очевидность: единица и само n в качестве множителей не допускаются :) 15 апр 2017 в 16:28

2 ответа 2

2

Разлагаем число на простые сомножители - факторизация на этом сайте разбиралась неоднократно. Допустим, это

введите сюда описание изображения

Если сумма всех l не меньше k - то можно :) Как вывести такое разбиение - понятно? Код писать не нужно?

Можете посмотреть ответы на этот вопрос.

2
  • k раз разлогать надо верно ? 15 апр 2017 в 16:13
  • Разлагать число n на сомножители. Например, n = 2^2*3^1*5^2 = 300 Так как 2+1+2=5, это число можно разложить до 5 множителей. На 6 и более - нельзя. Например, на 4: 300=2*2*3*25...
    – Harry
    15 апр 2017 в 16:23
1

Чтобы набрать k множителей, можно начать с 2 и увеличивать по одному пока все простые множители не закончатся или пока k множителей не наберётся, добавляя оставшийся множитель в конце (предполагая, что множители не могут быть равны n или 1 иначе ответ для любого k > 0 был бы: n и k-1 единиц -- исключая тривиальный случай, когда k == 1 и n является множителем себя):

#include <vector>

template<class U>
std::vector<U> k_factors(U n, U k)
{
  std::vector<U> factors;
  if (k == 1) {
    factors.push_back(n);
    return factors;
  }
  else if (k > 1) {
    for (U f = 2; f*f <= n; ++f) {
      while (n % f == 0) { // found prime factor
        factors.push_back(f);
        n /= f;
        if (--k == 1 && n > 1) {
          factors.push_back(n);
          return factors; // found solution
        }
      }
    }
  }
  throw std::invalid_argument("Impossible");
}

Пример:

#include <cstdlib>      // exit
#include <iostream>
#include <string>       // stoul

int main(int argc, char* argv[])
{
  if (argc != 3) {
    std::cerr << "Usage: k-factors <n> <k>\n";
    std::exit(2);
  }

  try {
    auto n = std::stoul(argv[1]), k = std::stoul(argv[2]);
    for (auto f : k_factors(n, k)) std::cout << f << ' ';
    std::cout << std::endl;
  } catch(const std::exception& e) {
    std::cerr << e.what() << '\n';
    std::exit(1);
  }
}

Результат:

$ g++ -std=c++11 *.cc -o k-factors && ./k-factors 18446744073709551615 5
3 5 17 257 281479271743489 

В этом случае даже простое деление в лоб достаточно быстро работает. Хотя ./k-factors 18446744073709551557 2 может занять какое-то время ;) В этом случае полезно проверить является ли n или n/<small prime> составным (к примеру, используя Тест Миллера — Рабина).

Ваш ответ

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

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