Anda harus menulis sebuah program atau fungsi yang memberikan tiga bilangan bulat positif n b k
sebagai input output atau mengembalikan k
digit terakhir sebelum nol trailing di b
representasi dasar n!
.
Contoh
n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013
Memasukkan
- 3 bilangan bulat positif di
n b k
mana2 <= b <= 10
. - Urutan bilangan bulat input dapat dipilih secara sewenang-wenang.
Keluaran
- Daftar digit yang dikembalikan atau dikeluarkan sebagai integer atau daftar integer.
- Angka nol di depan adalah opsional.
- Solusi Anda harus menyelesaikan contoh uji kasus di bawah satu menit di komputer saya (saya hanya akan menguji kasus tutup. Saya memiliki PC di bawah rata-rata.).
Contohnya
Tes baru ditambahkan untuk memeriksa kebenaran pengiriman. (Mereka bukan bagian dari aturan runtime di bawah 1 menit.)
Input => Output (dengan pilihan menghilangkan nol terkemuka)
3 10 1 => 6
7 5 4 => 3013
3 2 3 => 11
6 2 10 => 101101
9 9 6 => 6127
7 10 4 => 504
758 9 19 => 6645002302217537863
158596 8 20 => 37212476700442254614
359221 2 40 => 1101111111001100010101100000110001110001
New tests:
----------
9 6 3 => 144
10 6 3 => 544
Ini adalah kode-golf, sehingga entri terpendek menang.
code-golf
number-theory
base-conversion
factorial
randomra
sumber
sumber
7 5 3
menghasilkan "013" atau "13"?7 10 4
test case yang akan saya katakan13
n
atauk
? Atau bisakah kita membatasi mereka pada rentang tipe integer bahasa?Jawaban:
Dyalog APL , 23 byte
Program ini berfungsi selama faktorial tidak melebihi batas representasi internal. Di Dyalog APL, batas dapat dinaikkan oleh
⎕FR←1287
.Asumsikan variabel n, b, dan k telah disetel (mis.
n b k←7 5 4
), Tetapi jika Anda lebih suka meminta n , b , dan k (dalam urutan itu) maka ganti ketiga karakter dengan⎕
.sumber
Mathematica,
5748 byteDisimpan 9 byte berkat @ 2012rcampion.
sumber
b
terlebih dahulu untuk menghemat 2 byte?IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&
(baik ini dan sumber asli Anda cukup cepat)SlotSequence
trik yang saya gunakan dalam komentar saya hanya berfungsi dengan pesanan saat ini, sehingga Anda tidak dapat menyimpan lagi.Python,
198192181 karakterCukup cepat, ~ 23 detik pada contoh terbesar. Dan tidak ada faktorial bawaan (Saya melihat Anda, Mathematica!).
sumber
[2,3,2,5,3,7,2,3,5][b-2]
bisaint('232537235'[b-2])
untuk menghemat 3 byte.[1,1,2,1,1,1,3,2,1][b-2]
demikian pula.111973>>2*(b-2)&3
bahkan lebih pendek. Ini adalah jumlah byte yang sama untuk yang sebelumnya (90946202>>3*(b-2)&7
).Pyth,
2635 byteIni adalah fungsi dari 3 argumen, angka, basis, jumlah digit.
Demonstrasi.
Kasing uji paling lambat, yang terakhir, membutuhkan waktu 15 detik pada mesin saya.
sumber
PARI / GP, 43 byte
Kecepatan perdagangan untuk ruang menghasilkan algoritma langsung ini:
Masing-masing kotak uji beroperasi dalam waktu kurang dari satu detik di mesin saya.
sumber
Mathematica - 48 byte
Tidak Disatukan:
Contoh:
Untuk kasus terbesar, faktor pembatas tidak menghasilkan digit:
Pencocokan pola tampaknya
O(n^2)
, menyebabkan dua kasus uji terakhir melampaui batas satu menit.sumber
Bash / coreutils / dc, 60 byte
Menggunakan
dc
skrip dari jawaban saya untuk Find the Factorial , menghasilkan basis$2
, dengansed
memotongtail
garis nol dan untuk memilih$3
digit terakhir .sumber
rev
untuk mengurangi backtracking, tapi itudc
yang memakan CPU ...Haskell,
111109 bytePenggunaan:
f 158596 8 20
->[3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]
Memakan waktu sekitar 8 detik untuk
f 359221 2 40
laptop saya yang berumur 4 tahun.Cara kerjanya: lipat multiplikasi (
*
) ke dalam daftar[1..n]
. Konversikan setiap hasil antara menjadi basisb
sebagai daftar angka (paling tidak penting terlebih dahulu), lepaskan nol di depan, lalu ambilk
angka pertama dan konversikan ke basis 10 lagi. Akhirnya konversikan ke basisb
lagi, tetapi dengan digit paling signifikan terlebih dahulu.sumber
Python 3, 146 byte
Saya tidak yakin semua test case akan berjalan cukup cepat - yang lebih besar sangat lambat (karena perulangan melalui angka).
Cobalah online di sini (tapi hati-hati).
sumber
Java,
303299296 byteDi komputer saya, ini rata-rata sedikit di bawah sepertiga detik di
359221 2 40
testcase. Mengambil input melalui argumen baris perintah.sumber
bc, 75 byte
Ini menggunakan beberapa ekstensi GNU untuk mengurangi ukuran kode; setara dengan POSIX-sesuai memiliki 80 byte:
Agar waktu berlari masuk akal, kami memotong nol trailing (
while(!x%b)x/=b
) dan memotong kek
angka akhir (x%=b^k
) saat kami menghitung faktorial (for(x=1;n;)x*=n--
).Program uji:
Runtime dari test suite lengkap kira-kira 4¼ detik pada workstation 2006-vintage saya.
sumber
bc
program pertama saya (golf atau tidak), jadi setiap tips sangat disambut ...PHP, 80 byte
Digunakan sebagai
f(359221,2,40)
kasus uji terakhir. Berjalan cukup lancar untuk semua test case.Coba di sini!
sumber