Dengan bilangan bulat N , hitung berapa banyak cara yang dapat diekspresikan sebagai produk dari M bilangan bulat> 1.

Masukan hanya N dan M , dan output adalah jumlah total yang berbeda kelompok integer. Berarti Anda dapat menggunakan bilangan bulat lebih dari sekali, tetapi setiap grup harus berbeda ( 3 x 2 x 2tidak akan dihitung jika 2 x 2 x 3ada).

Kendala

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

Contohnya

Input 30 2memberi output 3, karena dapat diekspresikan 3 cara:

2 x 15
3 x 10
5 x 6

Input 16 3menghasilkan output 1, karena hanya ada satu grup yang berbeda:

2 x 2 x 4

Input 2310 4menghasilkan 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

Input 15 4memberi output 0, karena tidak bisa dilakukan.

Aturan

Berlaku celah kode golf standar, bersama dengan definisi standar untuk input / output. Jawaban dapat berupa fungsi atau program lengkap. Fungsi bawaan untuk faktorisasi dan / atau partisi tidak diizinkan, tetapi yang lain baik-baik saja. Kode dihitung dalam byte.

Pyth - 24 23 22 21 byte

Bukan solusi yang rumit. Akan lebih banyak bermain golf. Hanya mengambil produk cartesian dari daftar dan filter. Strategi yang sama dengan @optimizer (saya menduga karena komentarnya, tidak benar-benar menguraikan CJam itu) Terima kasih kepada @FryAmTheEggman untuk 2 byte dan trik dengan M.

Ml{m`Sdfqu*GHT1G^r2GH

Menentukan fungsi gdengan args GdanH

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

Bekerja pada semua argumen pengujian kecuali yang terakhir, terlalu lambat untuk yang satu itu tetapi tidak ada batas waktu yang diberikan.

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

Kami menghitung pembagi potensial i. Dengan argumen tambahan isebagai pembagi terendah yang diizinkan, relasi inti rekursif adalah

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

Untuk setiap i, kami memilih untuk memasukkannya (mungkin karena mengulang), dalam hal ini kita membagi produk yang dibutuhkan Noleh idan penurunan M. Jika tidak, kami bertambah i1, tetapi hanya jika i<N, karena tidak ada gunanya memeriksa pembagi lebih dari N.

Ketika pembagi minimum imelebihi N, tidak ada lagi pembagi potensial. Jadi, kami memeriksa apakah kami berhasil melihat apakah M==0 and N==1, atau, ekuivalen, M+1==N==1atau M+1==N<2, sejak kapan M+1==N, nilai timbal balik dijamin menjadi bilangan bulat positif (terima kasih kepada FryAmTheEggman untuk pengoptimalan ini).

Kode ini akan menyebabkan stack overflow Nsekitar 1000 pada kebanyakan sistem, tetapi Anda dapat menjalankannya di Stackless Python untuk menghindari hal ini. Selain itu, ini sangat lambat karena percabangan rekursif eksponensial.

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}

Sebenarnya cukup efisien untuk definisi rekursif. Untuk setiap pasangan pembagi [d,q]n, dengan dyang lebih kecil, kami menjumlahkan hasilnya f[q,m-1]. Bagian yang sulit adalah bahwa dalam panggilan batin, kita membatasi faktor yang lebih besar atau sama dengan d sehingga kita tidak berakhir dengan penghitungan ganda.

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 byte

Ini bisa menjadi jauh lebih pendek tetapi saya telah menambahkan cek tertentu untuk membuatnya bekerja untuk jumlah yang layak Mdi kompiler online.

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

Cobalah online di sini

T-SQL 456 373

Saya yakin ini akan pecah ketika inputnya bahkan mendekati besar.

Terima kasih kepada @MickyT karena telah membantu menyelamatkan banyak karakter dengan CONCAT dan SELECTing alih-alih beberapa 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)