Учитывая целое число N , подсчитайте, сколько способов его можно выразить как произведение M целых чисел> 1.

Входными данными являются просто N и M , а выходными данными является общее количество различных целочисленных групп. Это означает, что вы можете использовать целое число более одного раза, но каждая группа должна быть отдельной ( 3 x 2 x 2не будет учитываться, если 2 x 2 x 3присутствует).

Ограничения

1 < N <2 ³¹
1 < M <30

Примеры

Ввод 30 2дает вывод 3, так как он может быть выражен 3 способами:

2 x 15
3 x 10
5 x 6

Ввод 16 3дает вывод 1, так как есть только одна отдельная группа:

2 x 2 x 4

Ввод 2310 4дает вывод 10:

5 x 6 x 7 x 11
3 x 7 x 10 x 11
3 x 5 x 11 x 14
3 x 5 x 7 x 22
2 x 7 x 11 x 15
2 x 5 x 11 x 21
2 x 5 x 7 x 33
2 x 3 x 11 x 35
2 x 3 x 7 x 55
2 x 3 x 5 x 77

Ввод 15 4дает вывод 0, так как это не может быть сделано.

правила

Применяются стандартные лазейки для гольфа, а также стандартные определения для ввода / вывода. Ответы могут быть функцией или полной программой. Встроенные функции для факторизации и / или разделения не допускаются, но другие в порядке. Код считается в байтах.

Pyth - 24 23 22 21 байт

Не сложное решение. Будет больше играть в гольф. Просто берется декартово произведение списков и фильтров. Та же стратегия, что и у @optimizer (думаю, из-за его комментария, на самом деле не расшифровал CJam) Благодаря @FryAmTheEggman за 2 байта и трюк с M.

Ml{m`Sdfqu*GHT1G^r2GH

Определяет функцию gс аргументами GиH

M                    function definition of g with args G and H
 l                   length of
  {                  set (eliminates duplicates)
   m                 map
    `Sd              repr of sorted factors so can run set (on bash escape ` as \`)
    f                filter
     q      G        equals first arg
      u*GHT1         reduce by multiplication
     ^     H         cartesian product by repeat second arg
       r2G           range 2 to first arg

Работал над всеми тестовыми аргументами, кроме последнего, на этом был слишком медленным, но не было указано ограничение по времени.

Python 3, 59

f=lambda N,M,i=2:i<=N and f(N/i,M-1,i)+f(N,M,i+1)or-~M==N<2

Подсчитаем потенциальные делители i. С дополнительным аргументом iв качестве минимально допустимого делителя ядро ​​рекурсивного отношения

f(N,M,i)=f(N/i,M-1,i)+f(N,M,i+1)

Для каждого iмы либо решаем включить его (возможно, как повтор), в этом случае мы делим требуемый продукт Nна iи уменьшаем M. Если мы этого не сделаем, мы увеличим iна 1, но только если i<N, так как нет смысла проверять делители больше, чем N.

Когда минимальный делитель iпревышает N, потенциальных делителей больше нет. Итак, мы проверяем, добились ли мы успеха, проверяя, если M==0 and N==1, или, эквивалентно, M+1==N==1или M+1==N<2, с каких пор M+1==N, взаимное значение гарантированно будет положительным целым числом (спасибо FryAmTheEggman за эту оптимизацию).

Этот код вызовет переполнение стека на N1000 в большинстве систем, но вы можете запустить его в Stackless Python, чтобы избежать этого. Более того, он чрезвычайно медленный из-за его экспоненциального рекурсивного ветвления.

Руби, 67

f=->n,m,s=2,r=0{m<2?1:s.upto(n**0.5){|d|n%d<1&&r+=f[n/d,m-1,d]}&&r}

На самом деле достаточно эффективно для рекурсивного определения. Для каждой пары делителей [d,q]n, dбудучи меньшей, мы суммируем результат f[q,m-1]. Сложность состоит в том, что во внутренних вызовах мы ограничиваем факторы до значений, больших или равных d, чтобы мы не заканчивали двойной счет.

1.9.3-p327 :002 > f[30,2]
 => 3 
1.9.3-p327 :003 > f[2310,4]
 => 10 
1.9.3-p327 :004 > f[15,4]
 => 0 
1.9.3-p327 :005 > f[9,2]
 => 1 

CJam, 48 байтов

Это может быть намного короче, но я добавил некоторые проверки, чтобы заставить его работать приличное количество Mна онлайн-компиляторе.

q~\:N),2>{N\%!},a*{_,2/)<m*{(+$}%}*{1a+:*N=},_&,

Попробуйте онлайн здесь

T-SQL 456 373

Я уверен, что это сломается, когда входные данные даже близки к тому, чтобы быть большими.

Спасибо @MickyT за помощь в сохранении большого количества символов с помощью CONCAT и SELECTing вместо нескольких SET.

CREATE PROC Q(@N INT,@M INT)AS
DECLARE @ INT=2,@C VARCHAR(MAX)='SELECT COUNT(*)FROM # A1',@D VARCHAR(MAX)=' WHERE A1.A',@E VARCHAR(MAX)=''CREATE TABLE #(A INT)WHILE @<@N
BEGIN
INSERT INTO # VALUES(@)SET @+=1
END
SET @=1
WHILE @<@M
BEGIN
SELECT @+=1,@C+=CONCAT(',# A',@),@D+=CONCAT('*A',@,'.A'),@E+=CONCAT(' AND A',@-1,'.A<=A',@,'.A')END
SET @C+=CONCAT(@D,'=',@N,@E)EXEC(@C)