Ostatnia niezerowa cyfra n!


22

Biorąc na wejściu liczbę całkowitą 1 ≤ N ≤ 1 000 000 , wypisz ostatnią niezerową cyfrę N! gdzie ! jest silnią (iloczyn wszystkich liczb od 1 do N włącznie). Jest to sekwencja OEIS A008904 .

Twój program musi zakończyć się w ciągu 10 sekund na rozsądnej maszynie dla każdego ważnego wejścia.

Przypadki testowe

1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4

To jest więc wygrywa najkrótszy kod w bajtach!


Pojedyncza funkcja czy pełny program?
Joey,

@joey Nie, to tylko przypadki testowe. Pojedyncze wejście, jedno wyjście.
fR0DDY

@joey Kompletny program.
fR0DDY


2
@EriktheOutgolfer to pochodzi z ~ 7 lat temu, więc nie sądzę, żeby to było w tym czasie
ustalone

Odpowiedzi:


8

Rubin - 63 znaki

f=->n{n<2?1:6*[1,1,2,6,4,4,4,8,4,6][n%10]*3**(n/5%4)*f[n/5]%10}

Źródło - http://oeis.org/A008904

Obsługuje f do tysiąc cyfr w ciągu sekundy.

Test

irb(main):014:0> for n in 2..6
irb(main):015:1> puts f[10**n]
irb(main):016:1> end
4
2
8
6
4

11

Mathematica, 45 36 bajtów

Last@Select[IntegerDigits[#!],#>0&]&

Bardzo czytelny dla zwycięskiej odpowiedzi. :) (Z drugiej strony, nie ma jeszcze zgłoszenia GolfScript & Co.).

To obsługuje wejście 1 000 000 w około 5 sekund na moim komputerze.


1
Mathematica jest właściwie idealnym językiem dla tego pytania.
Michael Stern

4

Python - 75

n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10

3

PARI / GP - 27 bajtów

Szybkość wymiany zależy od rozmiaru - testowanie zajmuje dużo czasu (~ 6 sekund).

n->n!/10^valuation(n!,5)%10

Ta wersja jest znacznie szybsza (~ 15 mikrosekund), ale zajmuje 81 bajtów:

n->r=1;while(n,r*=Mod(4,10)^(n\10%2)*[1,2,6,4,2,2,4,2,8][max(n%10,1)];n\=5);lift(r)

Możesz użyć tego (nie golfowego) kodu do przetestowania:

[%(10^n) | n <- [1..6]]

2

Windows PowerShell, 53 56 59 60 63 73 90

($a=1).."$input"|%{$a="$($a*$_)".trim('0')%1e7}
$a%10

Uwagi:

  • Zajmuje więcej niż minutę dla liczby bliskiej 100 000. Jednak usunięcie zer na końcu wymaga konwersji na ciąg, wykonywanie obliczeń wymaga liczby, więc konwersje są nieuniknione.

Historia:

  • 2011-02-08 10:31 (90) - Pierwsza próba.
  • 2011-02-08 10:33 (73) - Moduł jest krótszy niż krojenie i łączenie.
  • 2011-02-08 10:34 (63) - Niepotrzebne wykończenie.
  • 2011-02-08 10:37 (60) - Niepotrzebna obsada na numer. Moduł już tak dobrze sobie radzi.
  • 2011-02-08 10:40 (59) - Niektóre inlining.
  • 2011-02-08 11:00 (56) - Co mówiłem wcześniej o tym, że moduł jest krótszy? Dotyczy również wyjścia.
  • 2011-02-08 11:01 (53) - $inputWystarczy rzut na sznur; rzutowanie intjest stosowane domyślnie.

2

Perl, 53 58 61 postacie

Wszystkie białe znaki można usunąć, ale pozostawiłem to dla „czytelności”. Uwaga: nie używanie jakiejś głupiej, jawnej formuły Sloane.

sub f {
    $_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $_[0];
    $1 % 10
}

Oblicza f (10 ^ 6) w 8,7 sekundy na mojej maszynie.

Aktualizacja : OP chciał, aby był to cały program:

$_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $ARGV[0];
print $1 % 10

To daje 55 znaków.


2

CJam - 28

1ri{I)*_AbW%{}#A\#/1e7%}fIA%

Możesz spróbować na http://cjam.aditsu.net/ dla wartości do około 10000; w przypadku większych liczb należy użyć interpretera Java . 1000000 działa na moim laptopie w około 3 sekundy.

Wyjaśnienie:

Niestety, proste rozwiązanie jest zbyt wolne, więc po każdym pomnożeniu zachowuję tylko ostatnie 7 cyfr (przed końcowymi zerami).

1           push 1 on the stack
ri          read a token and convert to integer
{           loop (for I from 0 to N - 1)
    I)      push I and increment
    *       multiply with the previous value (initially 1)
    _Ab     duplicate and convert to array of digits
    W%      reverse array
    {}#     find the position of the first non-zero digit
    A\#     raise 10 to that power
    /       divide, thus removing all trailing zeros
    1e7%    keep the remainder modulo 10000000
}fI         end for loop
A%          get the last digit

Uwaga: ten język jest znacznie nowszy niż pytanie.



2

05AB1E , 4 bajty

!0м¤

Wypróbuj online!

Wyjaśnienie

!0    # Push the factorial of the input and 0
  м   # Remove the occurences of 0 in the factorial
   ¤  # Push the last element, implicit display

1
Wersja TIO przekroczyła limit czasu (60s) w ostatnim przypadku testowym - jak udało ci się uzyskać w ciągu 10 sekund na „rozsądnej maszynie”?
Toby Speight

2

Galaretka , 4 bajty

!Ṛȯ/

Wypróbuj online!

Wyjaśnienie

Wykorzystuje fakt, że kiedy (odwraca listę; nie wektoryzuje) jest stosowana do liczby całkowitej, Dnajpierw automatycznie pobiera (cyfry).

Z wejściem 8:

!Ṛȯ/
!     Factorial: 8! = 40320
 Ṛ    Reverse: [0,2,3,0,4]
   /  Reduce by...
  ȯ   ...logical OR: ((((0ȯ2)ȯ3)ȯ0)ȯ4) = first truthy element = 2

Nie sądzę, że istnieje jeden bajtowy „pierwszy element zgodny z prawdą” (który ȯ/działa jako), ale jeśli tak, to można go skrócić do trzech bajtów ogółem.


2

Java (OpenJDK 8) , 62 bajty

n->{long f=n;for(;n>1||f%10==0;)f=n>1?f*--n:f/10;return f%10;}

Wypróbuj online!

Podobne do @Kevin Cruijssen, ale oszczędza 5 bajtów, łącząc pętle.


Witamy w PPCG! Miły pierwszy post! Mam nadzieję, że zostaniesz!
Rɪᴋᴇʀ

Witamy w PPCG! Zgadzam się z @Riker, świetny pierwszy post. Dobra gra w golfa w moim kodzie przez połączenie pętli. Można golf 1 więcej bajt w bieżącej odpowiedzi wymieniając ||z |, oraz dodatkowy bajt zastępując ==0z <1. Miłego pobytu!
Kevin Cruijssen

2

C, 150 140 135 bajtów

r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}

To jest wersja dla systemów ASCII; wymienić łańcuch 33436ze 11214dla systemu EBCDIC, lub \1\1\2\1\4na przenośnym programem.

Rozwiązania w C są nieco utrudnione przez wymóg zapewnienia pełnego programu; to jednak w pełni odpowiada na pytanie.

Wypróbuj online (wymaga Javascript):

Wyjaśnienie

Opiera się na algorytmie przedstawionym w Najmniej znaczącej niezerowej cyfrze n! , odwrócił się, abyśmy znaleźli najwyższą potęgę pięciu i dokonali obliczeń po wyjściu. Tabele stałych były zbyt duże, więc zmniejszyłem je, znajdując związek między poprzednią resztą r, bieżącą cyfrą di głębokością rekurencji k:

     0    1       2       3    4  =d
  0  0  3×2^k  1×2^2k  3×2^3k  2
  1  1  1×2^k  2×2^2k  1×2^3k  4
r 2  2  2×2^k  4×2^2k  2×2^3k  3
  3  3  3×2^k  3×2^2k  3×2^3k  2
  4  4  4×2^k  4×2^2k  4×2^3k  1

Bo r>0to rozwiązuje się do stałych czasów rrazy 2^dk(mod 5); stałe znajdują się a[]poniżej (wstawione w kodzie golfowym). Obserwujemy również, że (2^4)%5wynosi 1, więc możemy zmniejszyć wykładnik, aby uniknąć przepełnienia zakresu int.

const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x){
    int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
    int d = x%5;
    if (!d)
        return r;
    return r * a[d] * (1<<d*k%4) % 5;
}

int main(int c, char **v)
{
    c = atoi(*++v);
    printf("%d",
           c<2
           ? 1                  /* special-case 0 & 1 */
           : 2*f(0,c));         /* otherwise, it's 2 times r */
}

Testy:

$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4

Wydajność jest również godna szacunku. Oto maksymalne wejście dla systemu z 32-bitami int:

$ time ./694 2147483647
8
real    0m0.001s
user    0m0.000s
sys     0m0.000s

Mam te same czasy przy maksymalnym 64-bitowym int.


1
Warto zauważyć, że 2147483647!ma on ponad 19 miliardów cyfr i (2^63-1)!ponad 170 000 000 000 000 000 000 000 cyfr, więc jest to duża wygrana w stosunku do obliczania silni. 1000000!jak określono w pytaniu, możliwe jest obliczenie na obecnym sprzęcie; to tylko 5,5 miliona cyfr. :-)
Toby Speight

1

PHP - 105

 <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";}

Działa poniżej 10 sekund z podaną walizką testową.


1

Python3

239 znaków

Może zrobić 10000 w ~ 3,2 sekundy (Ideone odcina mnie po 8 sekundach, jestem pewien, że zajmie to więcej niż 10 sekund :()

from functools import *
N=100
r=range
s=(p for p in r(2,N)if all(p%n>0for n in r(2,p)))
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=list([p,f(N,p)]for p in s)
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:x[0]**x[1],e))%10)

Python2.6

299 znaków (nieco szybciej)

from itertools import *
N=100000
r=xrange
def s(c=count(2)):
        while 1:p=c.next();c=ifilter(p.__rmod__,c);yield p
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=[[p,f(N,p)]for p in takewhile(lambda x:x<N,s())]
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:pow(x[0],x[1],10),e))%10)

1

Haskell, 78 znaków

f n=head$dropWhile(=='0')$reverse$show$product[1..n]
main=interact(show.f.read)

(Prawdopodobnie trzeba go skompilować, aby obliczyć 1 000 000! W 10 sekund).


Zapisz dwóch znaków, należy wymienić, że foldl1z product(por codegolf.stackexchange.com/questions/607/find-the-factorial/... ). Ale czy rzeczywiście próbowałeś z 1000000! ?
JB

PS: niekompletny program.
JB

Przepraszam, zrobiłem to wcześniej, co zostało wyjaśnione w komentarzach. Zaktualizuję to.
stusmith

1

J - 42 40 znaków

Cały program. Zapisz ten program w pliku i uruchom z jconsole script.ijs 1234. Zauważ, że ten program nie wychodzi z interpretera po wydrukowaniu wyniku. Wpisz ^Dlub, exit]0aby wyjść z interpretera.

echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV

Oto wyjaśnienie:

  • x #. yinterpretuje wektor liczb całkowitych yjako xliczbę podstawową ; na przykład 10 #. 1 2 3 4daje 1234.
  • u invzwraca odwrotność czasownika u. W szczególności x #. inv yreprezentuje yjako xliczbę podstawową ; na przykład 10 #. 1234daje 1 2 3 4. Należy zauważyć, że invokreśla się jako ^:_1, że jest ustosowana -1 czasu.
  • x * yJest to produkt z xi yw ten sposób x 10&#.inv@* yuzyskuje się bazowym 10 przedstawienie produktu xi y.
  • x # ykopiuje n- ty element ytak często, jak n- ty element x; kiedy xjest wektorem wartości logicznych, xwybiera, które przedmioty ywziąć. Na przykład 1 0 1 0 # 1 2 3 4daje 1 3.
  • * yotrzymano signum się y.
  • x u~ yjest zwrotna od u, czyli taki sam jak y u x.
  • W ten sposób y #~ * yuzyskuje się wektor wszystkich elementów, yktóre są dodatnie. W milczącej notacji można to zapisać za pomocą haka jako (#~ *).
  • {: ydaje ostatni element w y.
  • zebrane razem otrzymujemy milczącą frazę ([:{:@(#~*)10&#.inv@*).
  • u/ yJest to zmniejszenie o y, to znaczy dwójkowym czasownik uwstawione pomiędzy elementami y. Na przykład +/1 2 3 4jest podobny 1 + 2 + 3 + 4i daje 10.
  • W ten sposób wyrażenie ([:{:@(#~*)10&#.inv@*)/ yzwraca ostatnią cyfrę iloczynu pozycji y.
  • ARGV jest zapakowanym wektorem argumentów wiersza poleceń.
  • ".>{:ARGV jest ostatnim argumentem rozpakowanym i interpretowanym jako liczba.
  • i. yoblicza liczby naturalne od 0do y - 1.
  • W ten sposób 1+i. yuzyskuje się liczby naturalne od 1do y. Mógłbym również użyć >: przyrostu tutaj, ale 1+jest jaśniejszy przy tym samym koszcie postaci.
  • Cały program po prostu stosuje 1+i.".>{:ARGV(wektor 1do liczby w ostatnim argumencie wiersza poleceń) do czasownika ([:{:@(#~*)10&#.inv@*)/i wypisuje wynik za pomocą echo.

1

Pyt , 5 bajtów

!₫ą0⦋

Wyjaśnienie:

         Implicit input (n)
!        n!
 ₫       Reverse the digits of (n!) - this disregards leading zeroes after reversal
  ą      Convert to array of digits
   0⦋    Get the first element

Wypróbuj online!


1

R , 63 55 51 46 bajtów

Oblicza silnię, wyodrębnia ostatnią niezerową cyfrę. Dzięki Giuseppe za zapewnienie podstawowej struktury.

(y=(gamma(scan()+1))%/%10^(0:1e5)%%10)[!!y][1]

Wypróbuj online!

Alternatywnie, moja stara 51-bajtowa odpowiedź:

Oblicza silnię, konwertuje na postać, usuwa wszystkie 0s, a następnie przyjmuje końcowy znak. Zaoszczędzono 2 bajty dzięki Giuseppe.

substring(x<-gsub("0","",gamma(scan())+1),nchar(x))

Wypróbuj online!


1
gamma(x+1)jest krótszy niżfactorial(x)
Giuseppe

bez konwersji ciągów najlepsze, co udało mi się uzyskać, to (y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]54 bajty.
Giuseppe,

@Giuseppe Możemy wymienić nchar(x)z 1e5rozwiązania 46-bajtowy! Miło się dzieje.
rturnbull


1

Perl 6 ,  26  35 bajtów

{[*](1..$_)~~/.*<(<-[0]>/}

Spróbuj


Jako pełny program:

put [*](1..@*ARGS[0])~~/.*<(<-[0]>/

Spróbuj

Rozszerzony:

{
  [*]( 1..$_ ) # reduce using &infix:« * »
  ~~           # match with
  /
    .*         # any number of values (so it matches from the end)
    <(         # only capture the following
    <-[0]>     # any value but 0 (negated character class)
  /
}

1

C (gcc) , 72 bajty (funkcja)

f(n,d)long long n,d;{for(d=1;n;d%=10000)for(d*=n--;d%10<1;d/=10);d%=10;}

Wypróbuj online!

C (gcc) , 101 99 bajtów (cały program)

main(){long long n,d=1;for(scanf("%lld",&n);n;d%=10000)for(d*=n--;d%10<1;d/=10);printf("%d",d%10);}

Wypróbuj online!

To pytanie jest po prostu nieśmiałe od 8 lat, więc „rozsądna maszyna” nie jest już taka sama jak wtedy, ale otrzymuję czasy ~ 0,01 sekundy na moim komputerze, kiedy wykonuję wszystkie przypadki testowe razem, więc chyba, że ​​komputery przyspieszyły 1000 razy w ciągu ostatniej dekady powinno być w porządku.


Prawo Moore'a wciąż (trochę) trzyma się, więc powinno być około x16 razy szybsze
tylko ASCII

Również funkcja jest w porządku
tylko


0

Attache , 26 bajtów

Last@`\&:(All@V)@Digits@`!

Wypróbuj online!

Wyjaśnienie

Last@`\&:(All@V)@Digits@`!

Jest to kompozycja 4 funkcji:

  • `! - jest to funkcjonalna wersja operatora silni
  • Digits - otrzymuje cyfry silni
  • \&:(All@V)- To jest funkcja wyboru. Działa poprzez zostawienie spojenia ( &:) funkcji All@Vdo \, co wybrać. Z kolei All@Vjest krótkim sposobem sprawdzenia, czy liczba nie jest równa 0. Działa poprzez rzutowanie danych wejściowych na wektor, 0 -> [0]a następnie sprawdzanie, czy wszystkie te elementy są zgodne z prawdą (tj. Nie 0). Daje to cyfry liczby bez zer.
  • Last - to po prostu uzyskuje ostatniego członka tej tablicy.

Wydaje się to niezwykle powolne - upłynął limit czasu TIO (1 minuta) w przypadku testowym 100000 - w jaki sposób uzyskano wynik 1000000 w ciągu 10 sekund?
Toby Speight

@TobySpeight Kiedy odpowiedziałem na to wyzwanie, nie było tego konkretnego wymagania (sprawdź historię zmian).
Conor O'Brien

Ach, powinienem był spojrzeć na historię! Jednak zweryfikowałeś wszystkie przypadki testowe w pytaniu?
Toby Speight

Wygląda na to, że w okresie, gdy termin został usunięty z pytania, pojawiło się mnóstwo odpowiedzi - to naprawdę niefortunne.
Toby Speight

@TobySpeight Tak, zrobiłem. To niefortunne i nie jestem pewien zasad dotyczących tego.
Conor O'Brien,

0

APL (Dyalog Unicode) , 18 15 bajtów

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘!

Wypróbuj online!

Funkcja ukrytego przedrostka. Zwraca poprawną cyfrę dla pojedynczego przypadku testowego lub ciąg cyfr dla wielu przypadków testowych.

Dzięki @ Adám i @ErikTheOutgolfer za 3 bajty każdy.

W jaki sposób?

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘!  Main function. Argument is a number following the !.
              !  Factorial
                then
                Format (stringify)
        ⍎¨⍵}     Execute (turn to number) each digit of the argument
      0         Check if each is 0. This returns a boolean vector
                Swap arguments for the following fn/op
   ⍵/            Replicate. This takes a boolean vector as left arg and returns the truthy elements of the right arg. E.g.: 1 1 0/1 2 3  1 2.
{⊢/              Reduce. This returns the rightmost (last) element of a vector argument.

0

APL NARS, 28 bajtów, 14 znaków

{↑≠v/v←⌽⍎¨⍕!⍵}

Nie wiem dlaczego, ale ten test zdał:

  q←{↑≠v/v←⌽⍎¨⍕!⍵}       
  q¨1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 6 4 2 2 4 2 8 8 8 6 8 2 

0

AWK , 47 57 bajtów

{for(p=$1;--$1;p=(p*$1)%1e4)while(!(p%10))p/=10;$0=p%10}1

Wypróbuj online!

Oryginalne rozwiązanie nie radziło sobie dobrze z „dużymi” wartościami wejściowymi. Można dodać, -Maby zmusić go do działania, ale wymaga to również dużo więcej czasu przetwarzania.


Tak, @TobySpeight, infnie %bardzo dobrze. :(
Robert Benson,

Ach ... patrząc na wersję pytania, na które odpowiedziałem, duże liczby nie były wymagane.
Robert Benson,

-2

Japt , 6 bajtów

Wymyśliłem kilka różnych 6-bajtowych, ale ten najbardziej mi się podobał. Jestem jednak przekonany, że musi być sposób, aby to zrobić w 5.

Êsw ìv

Spróbuj


Wyjaśnienie

Êoblicza silnię danych wejściowych, skonwertuje ją na ciąg znaków i wraca do liczby całkowitej po wodwróceniu go, ìkonwertuje wynik na tablicę cyfr i vzwraca pierwszy element.


Alternatywy

Êì w æ
ÊìÈf Ì
Êì f o
Êsw sg
Êìf ìo
Êìf ìÌ

Jak długo zajmuje wykonanie wszystkich przypadków testowych?
Toby Speight,

@TobySpeight; bardzo łatwo to przetestować, klikając link, aby go wypróbować. Pamiętaj, że ostatnie 4 przypadki testowe zakończą się niepowodzeniem, ponieważ ich silnia są większe niż maksymalna liczba całkowita JavaScript.
Kudłaty

Więc to tak naprawdę nie rozwiązuje problemu? Pytanie mówi, że musi się udać dla 1 ≤ N ≤ 1 000 000 . Inne odpowiedzi pokazują, że nie trzeba mieć możliwości przechowywania silni, aby obliczyć odpowiedź.
Toby Speight

Próbowałem testu online, ale upłynął limit czasu dla pierwszego testowanego przypadku (1000).
Toby Speight

-2

Perl 5 , 36 + 10 ( -p -Mbigint) = 46 bajtów

$"=$_;$_*=$"while$"-=1;($_)=/(.)0*$/

Wypróbuj online!


Wersja TIO kończy się niepowodzeniem w dwóch pierwszych testowanych przypadkach: 1000000 ⇒ f(powinno być 4 ) i 100 ⇒ 7(powinno być 4 )
Toby Speight

Przepełnia się rozmiar int. Nowa wersja działa przy użyciu bigint. Wydajność wciąż pozostawia wiele do życzenia, ponieważ jest to kalkulacja brutalnej siły. Oznacza to, że przekracza limit czasu dla TIO dla większych liczb.
Xcali
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.