Dado um número inteiro N , conte quantas maneiras ele pode ser expresso como um produto de M números inteiros> 1.

A entrada é simplesmente N e M e a saída é a contagem total de grupos inteiros distintos . Ou seja, você pode usar um número inteiro mais de uma vez, mas cada grupo deve ser distinto ( 3 x 2 x 2não contaria se 2 x 2 x 3estiver presente).

Restrições

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

Exemplos

A entrada 30 2fornece saída 3, pois pode ser expressa de três maneiras:

2 x 15
3 x 10
5 x 6

A entrada 16 3fornece saída 1, pois há apenas um grupo distinto:

2 x 2 x 4

Entrada 2310 4fornece saída 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

A entrada 15 4fornece saída 0, pois não pode ser feita.

Regras

Aplicam-se brechas de golfe de código padrão, juntamente com definições padrão de entrada / saída. As respostas podem ser uma função ou um programa completo. Funções internas para fatoração e / ou particionamento não são permitidas, mas outras são boas. O código é contado em bytes.

Pyth - 24 23 22 21 bytes

Não é uma solução complicada. Vai jogar mais. Apenas leva produto cartesiano de listas e filtros. A mesma estratégia do @optimizer (acho que por causa de seu comentário, na verdade não decifrou esse CJam) Graças a @FryAmTheEggman por 2 bytes e engane com M.

Ml{m`Sdfqu*GHT1G^r2GH

Define uma função gcom args GeH

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

O trabalho em todos os argumentos de teste, exceto o último, foi lento demais, mas não há limite de tempo.

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

Contamos potenciais divisores i. Com o argumento adicional icomo o divisor mais baixo permitido, a relação recursiva principal é

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

Para cada um i, escolhemos incluí-lo (possível como repetição); nesse caso, dividimos o produto necessário Npor ie diminuímos M. Se não o fizermos, aumentamos iem 1, mas apenas se i<N, já que não adianta verificar divisores maiores que N.

Quando o divisor mínimo iexcede N, não há mais divisores em potencial. Portanto, verificamos se conseguimos ver se M==0 and N==1, ou, equivalentemente M+1==N==1ou M+1==N<2, desde quando M+1==N, o valor mútuo é garantido como um número inteiro positivo (obrigado a FryAmTheEggman por essa otimização).

Esse código causará um estouro de pilha para Ncerca de 1000 na maioria dos sistemas, mas você pode executá-lo no Stackless Python para evitar isso. Além disso, é extremamente lento por causa de sua ramificação recursiva exponencial.

Ruby, 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}

Realmente razoavelmente eficiente para uma definição recursiva. Para cada par divisor [d,q]de n, dsendo o menor, somamos o resultado de f[q,m-1]. A parte complicada é que, nas chamadas internas, limitamos os fatores a valores maiores ou iguais a d, para não acabarmos contando duas vezes.

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 bytes

Isso pode ser muito mais curto, mas eu adicionei algumas verificações para fazê-lo funcionar com um número decente Mno compilador online.

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

Experimente online aqui

T-SQL 456 373

Tenho certeza de que isso quebrará quando as entradas estiverem perto de serem grandes.

Agradecemos ao @MickyT por ajudar a salvar muitos caracteres com CONCAT e SELECTing em vez de vários SETs.

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)