Étant donné un entier N , comptez combien de façons il peut être exprimé comme un produit de M entiers> 1.

L'entrée est simplement N et M , et la sortie est le nombre total de groupes entiers distincts . Cela signifie que vous pouvez utiliser un entier plus d'une fois, mais chaque groupe doit être distinct ( 3 x 2 x 2ne compterait pas s'il 2 x 2 x 3est présent).

Contraintes

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

Exemples

L'entrée 30 2donne la sortie 3, car elle peut être exprimée de 3 façons:

2 x 15
3 x 10
5 x 6

L'entrée 16 3donne la sortie 1, car il n'y a qu'un seul groupe distinct:

2 x 2 x 4

L'entrée 2310 4donne la sortie 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

L'entrée 15 4donne la sortie 0, car cela ne peut pas être fait.

Règles

Les failles de golf de code standard s'appliquent, ainsi que les définitions standard d'entrée / sortie. Les réponses peuvent être une fonction ou un programme complet. Les fonctions intégrées de factorisation et / ou de partitionnement ne sont pas autorisées, mais d'autres conviennent. Le code est compté en octets.

Pyth - 24 23 22 21 octets

Pas une solution compliquée. Jouera plus au golf. Prend juste un produit cartésien de listes et de filtres. Même stratégie que @optimizer (je suppose qu'en raison de son commentaire, n'a pas réellement déchiffré ce CJam) Merci à @FryAmTheEggman pour 2 octets et astuce avec M.

Ml{m`Sdfqu*GHT1G^r2GH

Définit une fonction gavec args GetH

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

A travaillé sur tous les arguments de test sauf le dernier, était trop lent sur celui-ci, mais aucune limite de temps n'est donnée.

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

Nous comptons les diviseurs potentiels i. Avec l'argument supplémentaire icomme le plus petit diviseur autorisé, la relation récursive de base est

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

Pour chacun i, nous choisissons de l'inclure (possible en tant que répétition), auquel cas nous divisons le produit requis Npar iet décrémentons M. Si nous ne le faisons pas, nous augmentons ide 1, mais seulement si i<N, puisqu'il ne sert à rien de vérifier les diviseurs supérieurs à N.

Lorsque le diviseur minimum idépasse N, il n'y a plus de diviseurs potentiels. Nous vérifions donc si nous avons réussi en voyant si M==0 and N==1, ou, de manière équivalente, M+1==N==1ou M+1==N<2, depuis quand M+1==N, la valeur mutuelle est garantie d'être un entier positif (merci à FryAmTheEggman pour cette optimisation).

Ce code provoquera un débordement de pile d' Nenviron 1000 sur la plupart des systèmes, mais vous pouvez l'exécuter en Stackless Python pour éviter cela. De plus, il est extrêmement lent en raison de sa ramification exponentielle récursive.

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

Effectivement raisonnablement efficace pour une définition récursive. Pour chaque paire [d,q]de diviseurs de n, détant la plus petite, nous additionnons le résultat de f[q,m-1]. La partie délicate est que dans les appels internes, nous limitons les facteurs à ceux supérieurs ou égaux à d afin de ne pas finir par un double comptage.

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 octets

Cela peut être beaucoup plus court mais j'ai ajouté certaines vérifications pour le faire fonctionner pour un nombre décent de Msur le compilateur en ligne.

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

Essayez-le en ligne ici

T-SQL 456 373

Je suis sûr que cela se cassera lorsque les entrées seront même proches d'être grandes.

Merci à @MickyT d'avoir aidé à sauver beaucoup de caractères avec CONCAT et SELECT au lieu de plusieurs 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)