Dado un entero N , cuente cuántas formas puede expresarse como producto de M enteros> 1.

La entrada es simplemente N y M , y la salida es el recuento total de distintos grupos enteros. Lo que significa que puede usar un número entero más de una vez, pero cada grupo debe ser distinto ( 3 x 2 x 2no contaría si 2 x 2 x 3está presente).

Restricciones

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

Ejemplos

La entrada 30 2da salida 3, ya que se puede expresar de 3 maneras:

2 x 15
3 x 10
5 x 6

La entrada 16 3da salida 1, ya que solo hay un grupo distinto:

2 x 2 x 4

La entrada 2310 4da salida 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

La entrada 15 4da salida 0, ya que no se puede hacer.

Reglas

Se aplican las lagunas de código de golf estándar, junto con las definiciones estándar de entrada / salida. Las respuestas pueden ser una función o un programa completo. Las funciones integradas para la factorización y / o particionamiento no están permitidas, pero otras están bien. El código se cuenta en bytes.

Pyth - 24 23 22 21 bytes

No es una solución complicada. Estaremos jugando más al golf. Solo toma producto cartesiano de listas y filtros. La misma estrategia que @optimizer (supongo que debido a su comentario, en realidad no descifró ese CJam) Gracias a @FryAmTheEggman por 2 bytes y truco con M.

Ml{m`Sdfqu*GHT1G^r2GH

Define una función gcon args GyH

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

Funcionó en todos los argumentos de prueba, excepto el último, fue demasiado lento en ese pero no hay límite de tiempo dado.

Pitón 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 divisores potenciales i. Con el argumento adicional icomo el divisor más bajo permitido, la relación recursiva central es

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

Para cada uno i, elegimos incluirlo (posible como una repetición), en cuyo caso dividimos el producto requerido Npor iy disminuimos M. Si no lo hacemos, aumentamos ien 1, pero solo si i<N, ya que no sirve de nada revisar divisores mayores que N.

Cuando el divisor mínimo iexcede N, no hay más divisores potenciales. Por lo tanto, verificamos si hemos tenido éxito al ver si M==0 and N==1, o, de manera equivalente, M+1==N==1o M+1==N<2, desde entonces M+1==N, se garantiza que el valor mutuo sea un número entero positivo (gracias a FryAmTheEggman por esta optimización).

Este código provocará un desbordamiento de la pila durante Naproximadamente 1000 en la mayoría de los sistemas, pero puede ejecutarlo en Stackless Python para evitar esto. Además, es extremadamente lento debido a su ramificación 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 razonablemente eficiente para una definición recursiva. Para cada par divisor [d,q]de n, dsiendo el más pequeño, sumamos el resultado de f[q,m-1]. La parte difícil es que en las llamadas internas, limitamos los factores a unos mayores o iguales a d para que no terminemos de contar dos veces.

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

Esto puede ser mucho más corto, pero he agregado ciertas comprobaciones para que funcione en un número decente Men el compilador en línea.

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

Pruébalo en línea aquí

T-SQL 456 373

Estoy seguro de que esto se romperá cuando las entradas estén incluso cerca de ser grandes.

Gracias a @MickyT por ayudar a guardar muchos caracteres con CONCAT y SELECTing en lugar de múltiples 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)