mocne zadanie Rodney: ZADANIE DLA NAJTWARDSZYCH A więc tak, robię zadanie na konkurs informatyczny i szukam jakiegoś sposobu na rozwiązanie... muszę napisać program, który poda ostatnią niezerową cyfrę takiej liczby: (a1+a2+ … +an)!/(a1!*a2!* … *an!) gdzie n≤20 Na koniec jest wskazówka: "Note that this is an extension of the classical problem, since factorials (and binomial numbers) are also multinomial numbers!" No i pytanie... jak to zrobić? a∊<0;10⁹>, wiec wyliczanie calej wartosci i potem szukanie ostatniej cyfry odpada, bo po prostu program nie policzy tak duzych wartosci... Jest ktos w stanie pomoc? Na poziomie liceum...

Jack: dla każdego i jest tak, że a_i∊<0,10⁹> ? Skoro jest to zadania na konkurs to na pewno nikt Ci nie pomoże Choć zadanie jest ciekawe...

Rodney: hmm... licze po prostu na to, ze moze ktos rzuci jakims pomyslem, bo ciezko mi zauwazyc jakas prawidlowosc tak, dla kazdego i jest taki przedzial co sprawia, ze zadanie staje sie nie do policzenia, trzeba znalezc jakis cwany sposob

b.: http://hs.spoj.pl/problems/HS12MULT/ ,,Termin nadsyłania rozwiązań I serii zadań został przesunięty o tydzień do poniedziałku dwudziestego drugiego października 2012'' nie jestem pewien, czy to zadanie jest z pierwszej serii, ale domyślam się, że tak > You may perhaps know how to find the last nonzero digit of n factorial. Wiesz?

Rodney: wlasnie... tego tez nie wiem... duzo kombinowalem, rozne opcje, ale wszystko dzialalo do pewnej granicy, nie moglem znalezc sposobu uniwersalnego...

Artur_z_miasta_Neptuna: ja mam pewną propozycję: 1) zapisujemy każdą z liczb a_i w postaci 2^b₁*3^b₂*5^b₃*....... w jaki sposób? już podaję: for {k=1,k<='ileś', k++,

	ai
m=floor(		) // ck jest to k−ta liczba pierwsza
	ck

liczbaliczb_k = 0 for {j=1, j<=m, j++

	ai
liczbaliczbi,k += floor(		) // chyba tak się zapisywało sumowanie w kolejnych
	(ck)j

krokach } } 2) sumujemy potęgi tej samej liczby pierwszej z rozkładów różnych a_i //tu chyba sobie poradzisz // czyli mamy zapisaną liczbę a₁!*....*a_n! 3) robimy różnicę potęg tej samej liczby pierwsze z rozkładów licznika i mianownika // tu też chyba sobie poradzisz // czyli mamy zapisany ułamek w postaci z pkt (1) 4) 'odrzucamy' odpowiednią liczbę '2' i '5' z tego rozkładu (bo tylko iloczyn 2^x*5^x daje 'x' zer) x = min(α , β) // gdzie α to potęga '2', natomiast β to potęga '5' 5) każdą liczbę pierwszą w rozkładzie 'redukujemy' do jej ostatniej cyfry (cyfry jedności) 6) dokonujemy potęgowania każdej z nich przez odpowiednią potęgę (i od razu redukujemy do cyfry jedności) 7) mnożymy otrzymane cyfry jedności przez siebie i redukujemy do cyfry jedności 8) wywalamy wynik Plusy rozwiązania: − operacje dokonywane na relatywnie niskich liczbach (żadna liczba w pkt(1) nie przekracza √20*10⁹, później już tylko lecimy na cyfrach jedności) − operacje elementarne (dzielenie ... potęgowanie liczb mniejszych od 10 ... dodawanie i odejmowanie) Minusy rozwiązania: − mimo wszystko znaczna ilość operacji jaką musi wykonać program

	a
− konieczność wpisania wewnętrznych programów min(a,b) oraz floor(		)
	b

− konieczność pracy na ogromnej liczbie tablic (konieczny pomysł na jakieś rozwiązanie deklarowania dynamicznego liczby tablic i ich długości) − konieczność stworzenia SPRAWNEGO algorytmu do wyszukiwania liczba pierwszych mniejszych od .... −−−− i to jest najgorsze

b.: ja mam propozycję, żeby dyskusje na temat tego zadania odłożyć na po 22 października − to jest zadanie konkursowe, które powinno się jednak samodzielnie rozwiązywać