Wie viele Möglichkeiten gibt es, N als Produkt von M ganzen Zahlen zu schreiben?

12

Zählen Sie bei einer Ganzzahl N , auf wie viele Arten sie als Produkt von M Ganzzahlen> 1 ausgedrückt werden kann .

Die Eingabe ist einfach N und M , und die Ausgabe ist die Gesamtzahl verschiedener ganzzahliger Gruppen. Das heißt, Sie können eine ganze Zahl mehr als einmal verwenden, aber jede Gruppe muss unterschiedlich sein ( 3 x 2 x 2würde nicht zählen, wenn 2 x 2 x 3vorhanden).

Einschränkungen

1 < N <2 31
1 < M <30

Beispiele

Input 30 2liefert Output 3, da es auf drei Arten ausgedrückt werden kann:

2 x 15
3 x 10
5 x 6

Eingabe 16 3gibt Ausgabe 1, da es nur eine eindeutige Gruppe gibt:

2 x 2 x 4

Input 2310 4gibt Output 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

Eingabe 15 4gibt Ausgabe 0, da dies nicht möglich ist.

Regeln

Es gelten Standard-Code-Golf-Regelungslücken sowie Standarddefinitionen für die Eingabe / Ausgabe. Die Antworten können eine Funktion oder ein vollständiges Programm sein. Eingebaute Funktionen zur Faktorisierung und / oder Partitionierung sind nicht zulässig, andere sind jedoch in Ordnung. Code wird in Bytes gezählt.

Geobits
quelle
Was meinst du mit Partitionierung?
Optimierer
@Optimizer Gruppieren einer Liste in nicht überlappende Unterlisten. In einigen Sprachen ist dies bereits integriert, beispielsweise in Mathematica .
Geobits
Gibt es eine zeitliche Begrenzung? Ein besonders naiver Algorithmus könnte für einen großen Wert von M Jahrhunderte dauern. Einfache Dinge wie die Feststellung, dass es nur einen Faktor größer als sqrt (N) geben kann, helfen offensichtlich sehr.
Level River St
1
@steveverrill Angesichts der Obergrenze für N sollte es nur 30 (Prim-) Faktoren geben, was die Sache ziemlich beschleunigt. Fühlen Sie sich jedoch frei, naiv zu sein. Wenn Ihr Algorithmus wahrscheinlich nicht innerhalb weniger Stunden eine Antwort liefert, kann ein gut erklärter Proof of Concept den Wählern bei der Entscheidung helfen.
Geobits
Ein eingebautes Produkt, mit dem Sie kartesische Produkte aus zwei Listen erstellen können, ist zulässig?
Optimierer

Antworten:

5

Pyth - 24 23 22 21 Bytes

Keine komplizierte Lösung. Wird mehr golfen. Nimmt einfach kartesisches Produkt von Listen und Filtern. Gleiche Strategie wie @optimizer (ich vermute wegen seines Kommentars, habe diesen CJam nicht wirklich entschlüsselt) Danke an @FryAmTheEggman für 2 Bytes und Trick mit M.

Ml{m`Sdfqu*GHT1G^r2GH

Definiert eine Funktion gmit args GundH

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

Hat an allen Testargumenten mit Ausnahme des letzten gearbeitet, war an diesem zu langsam, aber es ist kein Zeitlimit angegeben.

Maltysen
quelle
In diesem Format ist die Eingabe in Ordnung.
Geobits
1
Pyth Golf Tipp: Wenn Sie zwei Argumente bekommen, es ist in der Regel kürzer Einsatz , Mdie die Funktion definiert gvon zwei Argumenten, Gund H. Dies ist , was ich für diese: Ml{msdfqu*GHT1G^r2GH. Immer schön, einen anderen Pyth-Benutzer zu sehen :)
FryAmTheEggman
@FryAmTheEggman aktualisiert danke für den Tipp.
Maltysen
1
Dies scheint eine falsche Antwort für die Eingabe zu geben 72 3, die 5 zurückgibt, aber es gibt tatsächlich 6 Antworten,(2, 2, 18), (2, 3, 12), (2, 4, 9), (2, 6, 6), (3, 3, 8)
Isaacg
1
@isaacg oh ok, ich werde es auf meine 21 char-Version zurücksetzen. Ich hätte nicht gedacht, dass es funktionieren würde, aber es schien so, also gehe ich zurück zum Repräsentanten. Danke für den Fang.
Maltysen
9

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

Wir zählen potenzielle Teiler auf i. Mit dem zusätzlichen Argument ials niedrigstem zulässigen Divisor ist die rekursive Kernrelation

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

Für jedes iProdukt wählen wir entweder die Angabe (als Wiederholung möglich). In diesem Fall teilen wir das gewünschte Produkt Ndurch iund dekrementieren es M. Wenn wir dies nicht tun, erhöhen wir uns um i1, aber nur, wenn i<Nes keinen Sinn macht, Teiler größer als zu überprüfenN .

Wenn der minimale Teiler iüberschritten wird N, gibt es keine potenziellen Teiler mehr. Wir überprüfen also, ob es uns gelungen ist, indem wir prüfen, ob M==0 and N==1oder gleichwertig M+1==N==1oder M+1==N<2seit wannM+1==N der gegenseitige Wert garantiert eine positive ganze Zahl ist (danke an FryAmTheEggman für diese Optimierung).

Dieser Code führt Nauf den meisten Systemen zu einem Stapelüberlauf von etwa 1000. Sie können ihn jedoch in Stackless Python ausführen , um dies zu vermeiden. Darüber hinaus ist es aufgrund seiner exponentiellen rekursiven Verzweigung extrem langsam.

xnor
quelle
Ich denke, Sie können verwenden-~M==N<2
FryAmTheEggman
@FryAmTheEggman Ich dachte, das würde falsch positive Ergebnisse liefern, aber in der Tat funktioniert es dank der gemeinsamen Einschränkungen für Mund N. Vielen Dank!
Xnor
4

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

Eigentlich einigermaßen effizient für eine rekursive Definition. Für jedes Divisorpaar [d,q]von n addieren dwir das Ergebnis von f[q,m-1]. Der knifflige Teil ist, dass wir in den inneren Aufrufen die Faktoren auf diejenigen begrenzen, die größer oder gleich d sind, damit wir nicht doppelt zählen.

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 
Histokrat
quelle
2

CJam, 48 Bytes

Dies kann viel kürzer sein, aber ich habe einige Checks hinzugefügt, damit es Mauf dem Online-Compiler funktioniert .

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

Probieren Sie es hier online aus

Optimierer
quelle
Das ist fehlerhaft. Versuchen Sie die Eingabe 2 1. Erwartete Leistung: 1. Tatsächliche Leistung: 0.
Peter Taylor
@PeterTaylor Seufzer. Fest.
Optimierer
2

T-SQL 456 373

Ich bin mir sicher, dass dies kaputt geht, wenn die Eingänge fast groß sind.

Vielen Dank an @MickyT für die Unterstützung beim Speichern vieler Zeichen mit CONCAT und SELECTing anstelle mehrerer 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)
Markierungen
quelle
Ich würde das gerne unterstützen, aber ich kann keinen einfachen Weg finden, es zu testen. Irgendwelche Ideen? Die Bestätigung von Drittanbietern, dass es funktioniert, ist auch gut.
Geobits
Ich bekomme ein paar Konvertierungsfehler, die ich ausgeführt habe (2012). Sie scheinen aus diesen Aussagen SET @C+=',# A'+@undSET @D+='*A'+@+'.A'SET @E+=' AND A'+(@-1)+'.A<=A'+@+'.A'
MickyT
Sie müssen auch reparieren SET @C+=@D+'=@N'+@E+' SELECT @'. Das @Nbefindet sich innerhalb der Anführungszeichen und liegt außerhalb des Bereichs, wenn Sie es ausführen @C. Außerdem denke ich, dass du am Ende Duplikate zählen
wirst
Jetzt habe ich es 2012 getestet. Es sollte funktionieren.
Markierungen
2
Funktioniert jetzt gut :) Ein paar Orte, an denen Sie einige Charaktere rasieren können. Versuchen Sie mit CONCAT, Ihre Zeichenfolgen zu erstellen. Dann kannst du das CONVERTs fallen lassen. Versuchen Sie es SELECT @+=1,@C+=CONCAT(...),@D+=CONCAT(...),@E+=CONCAT(...)in Ihrer WHILESchleife. Sollte dir eine vernünftige Nummer
ersparen