求 2016! 末尾第一個非零數字？

12-31

小學見過這個題，數字是2006。感覺這道題遠遠超出了小學難度，不知道有沒有比較好理解的思路。

數列問題，當然是上OEIS：

A008904 - OEIS

A008904a(n) = final nonzero digit of n!.

這裡面給了一個很好玩的演算法：

From Washington Bomfim, Jan 09 2011: (Start)
a(0) = 1, a(1) = 1, if n &>= 2, with
n represented in base 5 as (a_h, ... ,a_1,a_0)5,
t = sum{i = h, h-1, ... , 0} (a_i even),
x = sum{i=h, h-1, ... , 1}(sum{k=h, h-1, ... , i}(a_i)),
z = (x + t/2) mod 4, and y = 2^z,
a(n) = 6(y mod 2) + y(1-(y mod 2)).

我們來嘗試一下

2016 = (31031)5

t = 0

x = 3*4 + 1*3 + 0*2 +3*1 = 18

z = (18+0) mod 4 = 2

y = 2^2 = 4

a(2016) = 6*0 + 4*(1-0) = 4

答案完全正確，而且不需要動用各類核武器（比如MMA）！！！

這是為什麼呢？來看證明：

http://oeis.org/w/images/4/48/AlgLastFinal1.txt

先聲明，以下公式中，用

$a equiv b (mod p)$ 的表示a與b對p取模同餘（注意有括弧和同餘號 $equiv$ ）

$a = b mod p$ 表示a是b除以p的餘數（注意沒有括弧，前面是等號）

其實關鍵在於這個等式（來自Concrete Mathematics第4章練習40題）

對於素數p

$frac{n!}{p^{epsilon_p(n!)}} equiv (-1)^{epsilon_p(n!)}a_m!...a_1!a_0! (mod p)$

其中

$n = (a_m...a_1a_0)_p$ 是n的p進位表示

$epsilon_p(n!)=sum_{i=0}^mia_i$ 是n!中質因數p的數目

原書的證明是採用歸納的方式

令

$g(n)=n!/p^{epsilon_p(n!)}$

$f(n)=prod_{1 le k le n,p mid k}k=n!/p^{lfloor n/p floor}(lfloor n/p floor)!$

則

$g(n)=f(n)f(lfloor n/p floor)f(lfloor n/p^2 floor)...=f(n)g(lfloor n/p floor)$

另一方面

$f(n) equiv a_0!(p-1)!^{lfloor n/p floor} equiv a_0!(-1)^{lfloor n/p floor} (mod p)$ (這裡用了一下Wilson定理)

$epsilon_p(n!)=lfloor n/p floor+epsilon_p(lfloor n/p floor!)$

以下遞歸顯然。

然後在我們現在這個問題中：

令 $x=epsilon_5(n!)=sum_{i=0}^hia_i$ （這就是上面演算法中所用的x）

其中

$n=(a_h...a_1a_0)_5$ 是n的5進位表示

由上面這個恆等式可知

$frac{n!}{5^x}=(-1)^xa_h!...a_1!a_0!$

我們知道n!的質因數分解中，2的數目遠大於5的數目，所以n!末尾的0的數目是由5的數目決定的，也就是說，我們要求的就是 $I=frac{n!}{10^x}$ 的末位數。

$herefore 2^xI=2^xfrac{n!}{10^x}=frac{n!}{5^x} equiv (-1)^xa_h!...a_1!a_0! (mod 5)$

記 $m = x mod 4$

$herefore 2^mIequiv (-1)^ma_h!...a_1!a_0! (mod 5)$

令 $P=(a_h)!...(a_1)!(a_0)! mod 5$

$herefore Pequiv(a_h! mod 5)...(a_1! mod 5)(a_0! mod 5) (mod 5)$

顯然n的5進位表示中只可能出現數字0、1、2、3、4，它們的階乘除以5的餘數分別是1、1、2、1、4，注意到若ai是奇數則餘數為1，若ai是偶數則餘數為2^(ai/2)，所以

$P equiv 2^{t/2} (mod 5)$

其中

$t=sum_{i=0}^{h}a_i1_{{a_i is even}}$ （這就是上面演算法中所用的t）

$herefore 2^mIequiv(-1)^m2^{t/2}equiv(-1)^m2^{(t/2 mod 4)} (mod 5)$

令 $i = I mod 5$

$herefore 2^miequiv(-1)^m2^{(t/2 mod 4)} (mod 5)$

由於i是I除以5的餘數，而我們知道I的末位一定是偶數（當n&>1時），所以只要知道i，如果i是偶數，那麼I除以10的餘數就是i，如果i是奇數，那麼I除以10的餘數就是i+5。

我們接下來就可以列個表：

$m = x mod 4$

$u = t/2 mod 4$

$v = I mod 10$ (注意v是根據i推算出來的）

m 0 1 2 3 u v 0 6 2 4 8 1 2 4 8 6 2 4 8 6 2 3 8 6 2 4

其實到這裡為止，這個演算法的證明就已經完整了，不過上述演算法又做了一個簡化：

令 $z = (x + t/2) mod 4 = (m+u) mod 4$

觀察上表可以發現：

當z=0時，v=6

當z不等於0時，v=2^z

所以最後那幾步只是用來取代查表而已。

最後：

注意到這個做法（包括證明）用到的數學知識包括：

進位表示

同餘和同餘的運算

Wilson定理

一般Wilson定理會在講同餘的時候講到，小學奧數當中，同餘和進位肯定是講的，如果Wilson定理也講了（可以不要求證明只要求記住結論，雖然實際上證明也是初等的），那麼這道題可以算是小學奧數範圍內的。

（雖然一般小學生確實想不出來這些……但是高中奧賽那些東西一般高中生也想不出來吧！所以也無所謂的說啦！）

答案已修改完善

—————————————————————————

小學做法就是找規律然後各種強行裝逼...

—————————————————————————

高年級小學生這樣考慮：

最末位非零數為x的數(直接考慮x是偶數的情況)

1:乘上10k+1,10k+6這一類數都不會改變x值.

2:乘(10k+3)(10k+7)=100k2+100k+21也不變

3:同理乘(10k+2)(10k+8)不變

4:同理乘(10k+4)(10k+9)不變

然後就是區分小學生姿勢水平的時候了

因為以上討論最後只剩最麻煩的乘10k,10k+5了(統一看成5k)，事實上只有它倆真正影響了x值，其餘全都抵消了。

機智的小朋友發現2016!的2因子一定比5因子不知道多到哪裡去了，因而非零最末位是偶數，故非零末位是2,4,6,8時乘5出來仍是偶數為6,2,8,4而非1,7,3,9.(相當於÷2x10，由mx2?(m不是2和5的倍數)類數末位規律，這是不難看出的)

故是乘5的變化是2→6→8→4→...

而乘5k拿掉5本質上就是乘k，與上面討論的同理。

1、我們先略過所有5的倍數乘到2010 (1,2,3,4,6,7,8,9,11...這樣乘)

乘到10(實際是略去5乘到9)是6

以後次次抵消，一直是6，直到2010，繼續乘到2016就是6,2,6,4,4，最後是4.(略過2015)

2、現在把所有5k，5~2015一共403個數先除以5變成1,2,...,403再乘進來，相當於乘以了403!.(這就是遞歸了)(拿了403個5)

3、遞歸吧，介於小學生大部分不會用計算機，咱徒手遞歸：

①403!排掉所有5的倍數乘到400末位是6，再乘401,402,403，末位6.(這次拿了80個5)

②剩下5的倍數全部除以5相當於乘以80!，拿走5的所有倍數，乘出來末位是6.(拿了16個5)

③同理相當於乘以16!，末位是4.(拿走3個5)

④相當於乘以3!，是6.

4、現在末位是4x6x6x4x6=6(mod10)

(注意，現在除了拿了一堆素因子5出去，所有數都乘進去了，並且現在由於沒有5的倍數，末尾實際上是沒有0的，直接是6)

5、我們一共拿了3+16+80+403=502個5，現在滴水之恩湧泉相報，全部一個個乘回去，如前面所說，滿足6→8→4→2循環，6變8，8變4...循環節是4，所以最後是4.

大體只用到了最基本的同餘←_←

計算量還好吧233然而寫完之後才突然發現如果考察c模5的餘數大概能更簡便一點但是沒太大區別就懶的改了qwq(′?｀) ??

階乘數最右邊一個非零數字：通用解法

丟個鏈接

大意如此：首先求出最右邊非零數模5的餘數。如果是奇數，加5後對10取模。(顯然n &> 1時結果該非零數必為偶數)

而最右非零數模5的餘數求法如下：

(5k+t)! = 2^k*t!*k!

代碼如下：

#include& int a[] = {1, 2, 4, 3};//2^k % 5 int b[] = {1, 1, 2, 6, 4};//n! % 5 int solve(int n){//求n!的最右非零數 % 5 if(n &< 5) return b[n]; int t = n%5, k = n/5; return a[k%4]*solve(t)%5*solve(k)%5; } int main(){ int ans = solve(2016); if(ans1) ans =(ans+5)%10; printf("%d ", ans); return 0; }

秒出結果。

結果是4。

「能不能給一道我不會答的題啊（摳鼻）」

但願這是最後一次更新

這邊題主的要求很明顯了，要把自己的智商壓低到小學生水平來完成這題，所以最後，回歸一開始我用過的2、5分組的方法。這裡先不考慮2000以後的數字，來算一個2000！試試。

提出所有偶數的2就會得到一個集合A{1,2,3,……,1000}和1000個2，應該夠用了。

剩下還有一串奇數的集合B{1,3,5,7……,1999}

把裡面5的倍數全部都拿走，剩下的就是{1,3,7,9}大概200組的樣子。

上面的集合A的話，可以交出100組{1,3,7,9}。

1*3*7*9-&>9，看到9還是比較高興的，畢竟9的冪的個位就是9-&>1-&>9-&>1這麼變的2333。

那麼300組{1,3,7,9}直接就沒什麼用了，畢竟乘出來個位是1啦。

那麼我們現在手裡還剩下集合A裡面剩下的所有偶數，集合A1{2,4,6,8……,1000}、

1000個2，還有集合B剩下的5的倍數，記作B1{5,15,25,……,1995}，以及集合A裡面5的奇數倍A2{5,15,25……,995}。

看起來已經做得差不多了。

集合A1其實已經可以直接算結果了分成100組{2,4,6,8}和一組拿掉了末位的0的{1,2,3,……,100}。

100！的最小非零位像之前那樣算是沒問題的，11組{1,3,4,6,7,8,9},1組{12,25,22,25……92,95}，也就是4。然後2*4*6*8的個位是4,4^100個位是6。

集合A1的積的個位就是4。

目前只是還沒有把A2，B1和1000個2乘進去。

讓A2和B1裡面的第一批5見鬼去，那麼B1就變成了B2{1,3,5,……399}和200個5

A2就變成了A3{1,3,5,……,199}和100個5。

恩那我們就剩下A3、B2和700個2了，問題規模收斂的飛快。(-300個2)

B2裡面也就40組沒什麼用的{1,3,7,9}，直接扔了得到B3{5,15,25,……,395}

A3裡面也就20組沒什麼用的{1,3,7,9}，直接扔了得到A4{5,15,25,……,195}

可以再祭出60個2就可以得到B4{1,3,5,……,79}、A5{1,3,5,……,39}

還剩640個2(-60個2)

然後再拿出些2(-12個2)

B5{1,3,5,……,15}、A6{1,3,5,7}，還剩628個2。

B6{1,3,1,7,9,11,13,3}、A6{1,3,1,7}，還剩625個2。

B6和A6最後乘出來個位是1、625個2的結果是2。

那麼2000！的個位就可以得到了，就是4*1*2-&>8（撒花）

恩，做到這裡，其實只要重新按照這樣子的分組思路再做一遍就好。

當然也可以直接把2001到2016乘上去，中間注意2012*2015這組非零末尾是8的就好。

結果當然是4啦，那麼多回答都說了。

………………………………………………（這後面全是黑歷史啊喂）…………

最後還是通過寫程序找到了bug所在……所以說這個放到小學，至少我是不能分情況討論作出正確解答了，這個x75和x25也是bug般的存在，原因在於啊，這個x72必然是4的倍數。而這個x22*x25出來之後又是個x5的結構……這讓人怎麼愉快地玩耍嘛！！

題目還是要做，怎麼辦呢。就算解決的了這個x75和x25 後面肯定還有別的問題……

……………………………………………………

感覺還是算不對……似乎陷入了奇怪問題之中

1000！

分為111組末尾第一個非零數字是{1,3,4,6,7,8,9}

11組末尾兩個非零數字是{(02,05),(12,15),(22,25),(32,35),……,(92,95)}

那麼結果應該是8^111*2^11-&>6

(= =)容我好好想想，看來智商已經下降到小學生水平了。

然後乘到2000的時候只要注意1200和1500以及2000本身就可以了……

……………………………………………………

（下面是2016/6/20前的回答，大體思路反正也就是這樣子了，太輕視這道題了，望天）

……………………………………………………

2和5會配對成0所以就沒什麼用了

3*4*6*7*8*9的結果個位是8

8^1-&>8 8^2-&>4 8^3-&>2 8^4-&>6

-&>100!的第一個非零位由11組（3、4、6、7、8、9）得出應該是 2

（10組3、4、6、7、8、9 附帶10、20、30這組十位的貢獻，後面都可以同理）

-&>1000!的非零位是2

-&>2000!的非零位是8

然後再乘個8-&>2010!的非零位是4

再乘到16 那麼結果大概就很顯然了

是4

要說小學的解法，估計就是這樣子了，講究分組和觀察規律。

腦子寫期末作業有點混，不過演算法思路是沒問題的。

………………………………………………………………

有點強迫症想把答案改得完美，立刻發現了個問題，就是x2*x5是會進位的，果然智商已經嚴重下線了（望天）

12*15=180 8

22*25=550 55

32*35=1120 12

42*45=1890 9

52*55=2860 6

62*65=4030 3

72*75=5400 4

82*85=6970 7

92*95=8740 4

而這麼一組的乘積的最小非零位是2

那麼加到上述體系裡面加以考量的話，作出修正：

100！這裡應該會得出4

1000！這裡應該會得出8

2000！這裡應該會得出8

……後面用1*2*3*4*5*6和11*12*13*14*15*16驗算的時候發生了問題

………………………………………………

好想回去讀小學（看著大程和論文還有沒預習的課程望天）

答案是4，也用大數模擬過了

2016!=23258495818030913010031406857274860433285983443614934462402467595342154268778363275838685857644896458696421014249826747841767469881092389704938830363216731591155863356703754444857634376693945519803869169570029885668894353248805939318365845564846182939156029934858243838725776090388134705013830027815486707405808856169619884714709048478148779261865257398408587773826812390629129013902081905975233016501555686707276384951880671677970018345879552317540560485550456075007409472954061111457357312955870960882832895619175971461141211657061076557697120427218627496277170491990305753000102220356368830021241984048511892794666728766755594850295492123038246698402750124139296584506579637696633426680311156713967796805815732903954829738964781694383613752403405065518284999382284515504223343963218552949569245812930855510064598768442836209462650531832866214504494813124923040906814889298949251981359646977102914232598897187948213243763726465016850416907985252818361287376031060910864674497840750445579848210856498766637227108629478476187571564298442102848716297180400526415216789238537160993621915677499758518994798408323035221433583725552624955877475064577202903813029961349569252153606035327824905676258551065885255404545850784448860614966918098514952183294291514675958641275130196101961164681292559321302803390512025758230622589695643797621325191500289162337210614797563476403646193144041372441405455479972945179888790533231219846881531953169423774756920001751962338387559408901967171526226090976630763283682934472586320489244438769804460773480563029545020605868863451773477382003471169516906048382368449558208429492851517527799922645840168680391059891651465347112072330187589203513252698914382245604983528100471005169499165099809553591507877866610429512283501355120150287470249062265764748933171718819531951752263448908282307954229253069787688999851695000984552136097544465724167649889578291638834893090442546130089704873855224412714205708286796497452017250877941822097814829337355079016131428174220894709219804556425751596579526107858851551428153207116373736355399215164455409228737043792595202608153916678120376985137271711247402779066091315065795459592793140090819107259232230728531104447881228064722501037160118346108540653963812345814287459580769391949397014310942823752561057089811126611866003407022616450729022245461564026713011991430914295336722821794365635198791275381334582226216064733899379878352436168884120708140871292679304861853450730589510198573044251796943404387832651132207824144481261013392114061916352290480964047681024728575555087675438199670781633710224155370116491726628727463515602828861827015183247895266650223625334401157118619015804799076192226005411330777915152281471841459107377484730878884947396685197378979862377835321484737743822795384106157869335574433357160924806803855030347044758022091247894447391039288280726912344997466373245095207451203702680151464613045797673328379964702661987238163918493237037023459261924501977402444706721272845542403533928272696231194079729016396027951267701893145632268941847469078289403766574019936975398687206711729551608280812113921639143536575246278273452565643277697670885880881894705812438260661068982376645556066403743358818649208697123395353599161793408061889006817029132979618905090400730811823137075086689136868212332830578029434029389652567909544767573634619190789539608832454033416972801448226579334391784570284109220558519343746210225698221579157880636464860033156145873335772022285776683497885735765963512093361097184892159088872996171397077843396851183587217818054469695208085333113809159321253574934788901831341564290161581682647213012899887138866265414587272661116144948643445117700125471713463337901813217938395799379994475694166420884537470725284685143702728865492479498558118401960251559670962122337656908363038307575111514095451782601900236620926093412923195126196422996734766963940800350744163617376155683977740493693262048532875214937835029187729576949113396242399884384168456837523301341126289291219240077848565624856171119054644513387456321098668502208793628879286902533874940484934891004437760686327570879295464578144790279379075619388065480867891821106474778332831813350968875802584341831787599233331579169939801875490240459552789478834222049973435514849093156798602137570980204569004905184554467849861000269628871950235201246896027009100495698531554819744709154634601456538879980480955137401835963475321981062763214745630329506584110448926260464762858756763503919609265925302186328740341309500975676575281107527434451963698637448343314341520745178029714480078875382885464050163544774027918746196462571684990345285778503915057737119838265611069763744142112096036350178481973982149174891989022947043730094594907296786103156951400546568780469858982240049647541676112472599501277386102729400151541595896126986986147032717135102345799033476274063699491560343972090960078978365538648662481874599239710224468671642243131745533798215072496998699257731368868489085003385490206907277804396596276566726002586385583276407025978491218944361767383508525256428055353862662385556253281745982645564442567617550278838169420542539605852681692600240405938882944579907801553135863981895773258936312329505772305250936068518806856844794461455314392722254307732539043327099046363182761225868722787895669013336497177368219132887040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

代碼如下：

#include &

using namespace::std;

int main()

{

int n,i;

long int sum;

while(cin &>&> nn)

{

sum=1;

for(i=2;i&<=n;i++)

{

sum*=i;

while(sum%10==0)

sum/=10;

sum%=10000;//對10000取余是下限了，保證數的末尾不會被衝掉

}

cout &<&< sum%10 &<&< " ";

}

return 0;

}

純小學解法來了。

第一次在知乎寫回答，也不知道對不對，若有錯誤，請多包涵。

這個很簡單吧，分別考慮末尾為一到九的數組，找到模10的循環節，然後乘起來就行啊

之前要先消掉成對的2和5

嘗試來死算下吧。

我們用==&>來表示前面乘積的非0末位數。

先求6!和9!，5!=120，非0末位數是2。

6!==&>2;

7!==&>4;

8!==&>2;

9!==&>8;

========

上述這樣找規律感覺行不通，畢竟牽涉到進位的問題，求非0末位數還是得把2和5的因子都去掉，這樣剩下的數無論怎麼乘，由於末位永遠不會是0，反而容易了些。

考慮最後尾數相乘即可。個位數是0-9變化，2016/10=201餘6，尾數就是2016！=(1*2*3*4*5*6)^202*(7*8*9)^201=(72)^202*504^201=2^202*2^402=2^606=2^604*2*2=16^201*4=6*4=4

Wolfram|Alpha: Computational Knowledge Engine!

每次乘法的結果只保留末尾第一個非0的數字，循環往複！