Biorąc pod uwagę liczbę całkowitą N , policz, ile sposobów można wyrazić jako iloczyn liczb całkowitych M > 1.

Dane wejściowe to po prostu N i M , a dane wyjściowe to całkowita liczba różnych grup całkowitych. Oznacza to, że możesz użyć liczby całkowitej więcej niż jeden raz, ale każda grupa musi być odrębna ( 3 x 2 x 2nie liczyłaby się, jeśli 2 x 2 x 3jest obecna).

Ograniczenia

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

Przykłady

Dane wejściowe 30 2dają dane wyjściowe 3, ponieważ można je wyrazić na 3 sposoby:

2 x 15
3 x 10
5 x 6

Wejście 16 3daje wynik 1, ponieważ istnieje tylko jedna odrębna grupa:

2 x 2 x 4

Dane wejściowe 2310 4dają dane wyjściowe 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

Dane wejściowe 15 4dają dane wyjściowe 0, ponieważ nie można tego zrobić.

Zasady

Obowiązują standardowe luki w kodzie golfowym wraz ze standardowymi definicjami wejścia / wyjścia. Odpowiedzi mogą być funkcją lub pełnym programem. Wbudowane funkcje faktoryzacji i / lub partycjonowania są niedozwolone, ale inne są w porządku. Kod jest liczony w bajtach.

Pyth - 24 23 22 21 bajtów

Nie jest to skomplikowane rozwiązanie. Będzie więcej grał w golfa. Po prostu bierze kartezjański produkt list i filtrów. Taka sama strategia jak @optimizer (zgaduję z powodu jego komentarza, tak naprawdę nie odszyfrował tego CJam) Dzięki @FryAmTheEggman za 2 bajty i oszukać za pomocą M.

Ml{m`Sdfqu*GHT1G^r2GH

Definiuje funkcję gz argumentami GiH

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

Pracowałem nad wszystkimi argumentami testowymi oprócz ostatniego, był zbyt wolny na tym, ale nie podano limitu czasu.

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

Liczymy potencjalnych dzielników i. Z dodatkowym argumentem ijako najniższym dozwolonym dzielnikiem podstawowa relacja rekurencyjna to

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

Dla każdego z nich ialbo wybieramy to (możliwe powtórzenie), w którym to przypadku dzielimy wymagany produkt Nprzez ii zmniejszamy M. Jeśli nie, zwiększamy io 1, ale tylko wtedy i<N, gdy nie ma sensu sprawdzać dzielników większych niż N.

Kiedy minimalny dzielnik iprzekroczy N, nie ma już potencjalnych dzielników. Sprawdzamy więc, czy nam się udało, sprawdzając, czy M==0 and N==1, lub równoważnie, M+1==N==1lub M+1==N<2, od kiedy M+1==N, wzajemna wartość jest gwarantowana jako dodatnia liczba całkowita (dzięki FryAmTheEggman za tę optymalizację).

Ten kod spowoduje przepełnienie stosu dla Nokoło 1000 w większości systemów, ale można go uruchomić w Pythonie bez stosu, aby tego uniknąć. Co więcej, jest niezwykle wolny ze względu na wykładnicze rekurencyjne rozgałęzianie.

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}

Właściwie dość wydajny jak na definicję rekurencyjną. Dla każdej pary dzielników [d,q]n, przy dczym będąc mniejszą, sumujemy wynik f[q,m-1]. Problem polega na tym, że w wewnętrznych wywołaniach ograniczamy czynniki do tych, które są większe lub równe d, aby nie skończyć podwójnym liczeniem.

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 bajtów

To może być o wiele krótsze, ale dodałem pewne kontrole, aby działały na przyzwoitą liczbę w Mkompilatorze online.

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

Wypróbuj online tutaj

T-SQL 456 373

Jestem pewien, że to się zepsuje, gdy dane wejściowe będą nawet bliskie bycia dużymi.

Dzięki @MickyT za pomoc w uratowaniu wielu znaków dzięki CONCAT i SELECTing zamiast wielu zestawów.

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)