免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 求 2018! 的最后一个非零数字.

求 2018!的最后一个非零数字.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

$[\frac{2018}{5}]+[\frac{2018}{25}]+[\frac{2018}{125}]+[\frac{2018}{625}]=502$即2018!质因数分解后共有$5^{502}$,因为2的个数一定比5多,即2018!尾数一共有502个连续的零.难道要硬算,后面还不知道怎么做?
即要求$\frac{2018!}{10^{502}}$的个位数

TOP

MMC 算出的结果是 4

TOP

$[\frac{2018}{5}]+[\frac{2018}{25}]+[\frac{2018}{125}]+[\frac{2018}{625}]=502$即2018!质因数分解后共 ...
realnumber 发表于 2018-6-16 15:18

楼主的题我不会解(虽然很多方法,包括小学硬算,类题),你的问题的方向我却是了解的 翻任何一本初等数论 书的 同余部分,大致 需要用mod 2,5,10及中国剩余定理快速出结果。

TOP

谢谢!我也只能做到这里

TOP

本帖最后由 realnumber 于 2018-6-17 07:44 编辑

求 2018!的最后一个非零数字.
试着硬杠一下 ,设w(n),表示n的最后一个非零尾数,定义w(a,b)=w(ab),w(a,b,c)=w(abc),...
比如具有如下性质w(ae,be,ce,de)=w($e^4$,a,b,c,d),w(10a)=w(a)等,
那么w(2018!)=w(1,2,3,...,2018)
w(1,11,21,31,41,...,2011)=1
w(2,12,22,32,42,...,2012)=w($2^{202}$,1,6,11,16,...,1006)=w($2^{202}$,6)
w(3,13,23,33,...,2013)=w($3^{202}$)=9
w(4,14,24,34,...,2014)=w($2^{202}$,2,7,12,17,...,1007)=w($2^{202}$,$4^{101}$)=w($2^{202}$,4)
w(6,16,26,...,2016)=6
w(7,17,27,...,2017)=w($7^{202}$)=9
w(8,18,28,...,2018)=w($2^{202}$,4,9,14,19,...,1009)=w($2^{202}$,6)
w(9,19,29,...,2009)=w($9^{201}$)=9
以上8项乘积的最后一个非零尾数为w($2^{606}$,1,6,9,4,6,9,6,9)=w($2^{606}$,6)
还须计算以下2项,w(5,15,25,...2015),w(10,20,30,...2010)
w(5,15,25,...,2015,$2^{606}$)=w(10,30,50,70,90,...,4030,$2^{404}$)=w(1,3,5,7,9,...,403,$2^{404}$)
w(1,11,...,401)=1;w(3,13,...,403)=w($3^{41}$)=3;w(7,17,...,397)=w($7^{40}$)=1;w(9,19,...,399)=1
w(5,15,25,...,395,$2^{404}$)=w(10,30,50,...,790,$2^{364}$)=w(1,3,5,...,79,$2^{364}$), 到底要不要坚持下去?
因为w(1,3,7,9)=9=w(11,13,17,19)=...=w(71,73,77,79),所以w(1,3,5,...,79,$2^{364}$)=w(5,15,25,35,45,55,65,75,$2^{364}$)=w(10,30,50,70,90,110,130,150,$2^{356}$)=w(3,5,7,9,13,15,$2^{356}$)=w(3,10,7,9,13,30,$2^{354}$)=w(1,$2^{354}$)
w(5,15,25,...2015,$2^{606}$)=w(1,3,1,1,1,$2^{354}$)=w(3,$2^{354}$)
接着计算w(10,20,30,...2010)=w(1,2,3,...,201),不晓得还能不能算对?
w(1,2,3,11,12,13,21,22,23,...,191,192,193,201)=6
w(4,9,14,19,24,29,...,194,199)=6
w(7,8,...,197,198)=6=w(6,16,...,196)
w(5,15,25,...,195,$2^{354}$)=w(10,30,50,...,390,$2^{334}$)=w(1,3,5,7,9,...,39,$2^{334}$)=w(5,15,25,35,$2^{334}$)=w(10,30,100,70,$2^{329}$)=w($2^{329}$)
w(10,20,30,...,200,$2^{329}$)=w(1,2,3,...,20,$2^{329}$)=w(6,$2^{327}$)
这样最后结果是w(2018!)=w(6,3,6,$2^{327}$)=4, ,修改好了.
试着编了个程序,最后几位非零的是1623424,
对照kuing的处理,总体计算没规划好,2提得多了,象这样配成6,会好点w(4,4)=w(4,9)=w(7,8)=6=w(6,6)
当然有没简易的办法还需要探索.

TOP

回复 6# realnumber

先处理非5,再处理含5,结果最后分出来还要再处理非5,所以还不如一开始就处理含5。

TOP

回复 7# kuing

是迟钝多了,后来才慢慢发现的
不想改进了,留着更显得症状严重,对不?

TOP

回复 8# realnumber

因为 `\lfloor2018/5^4\rfloor=3`, `\lfloor2018/5^3\rfloor=16`, `\lfloor2018/5^2\rfloor=80`, `\lfloor2018/5\rfloor=403`, `3+16+80+403=502`,所以
\begin{align*}
w(2018!)=w(5^{502},&1,2,3,4,6,7,8,9,11,12,\ldots ,2018,\\
&1,2,3,4,6,7,8,9,11,12,\ldots ,403,\\
&1,2,3,4,6,7,8,9,11,12,\ldots ,79,\\
&1,2,3,4,6,7,8,9,11,12,\ldots ,16,\\
&1,2,3)
\end{align*}
然后每行再按照你前面的方法处理应该就可以了。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

你这样,不好处理,5会导致进位

TOP

回复 10# realnumber

你处理非5的时候不是会弄出一堆2出来吗?足以把那些5消掉啊

TOP

回复 11# kuing

对啊,明白了,但是我就大概这样做的啊

TOP

回复 12# realnumber

接我9#的:
\begin{align*}
w(2018!)=w(5^{502},&1,2,3,4,6,7,8,9,11,12,\ldots ,2018,\\
&1,2,3,4,6,7,8,9,11,12,\ldots ,403,\\
&1,2,3,4,6,7,8,9,11,12,\ldots ,79,\\
&1,2,3,4,6,7,8,9,11,12,\ldots ,16,\\
&1,2,3)
\end{align*}
仿你的处理方法:
\begin{align*}
&w(2,12,\ldots,2012,2,12,\ldots,402,2,12,\ldots,72,2,12,2)=w(2^{202+41+8+2+1},1,6,11,16,\ldots)=w(2^{254},6),\\
&w(3,13,\ldots,2013,3,13,\ldots,403,3,13,\ldots,73,3,13,3)=w(3^{254})=9,\\
&w(4,14,\ldots,2014,4,14,\ldots,394,4,14,\ldots,74,4,14)=w(2^{252},2,7,12,17,\ldots)=w(2^{252},4^{126})=w(2^{252},6),\\
&w(6,16,\ldots,2016,6,16,\ldots,396,6,16,\ldots,76,6,16)=6,\\
&w(7,17,\ldots,2017,7,17,\ldots,397,7,17,\ldots,77,7)=w(7^{251})=w(7^3)=3,\\
&w(8,18,\ldots,2018,8,18,\ldots,398,8,18,\ldots,78,8)=w(8^{251})=w(6\cdot 8^3)=2,\\
&w(9,19,\ldots,2009,9,19,\ldots,399,9,19,\ldots,79,9)=w(9^{250})=1,
\end{align*}
上式第一、三行已经有 `254+252=506` 个 `2`,与 `502` 个 `5` 消掉后还剩 `4` 个,所以
\[w(2018!)=w(2^4,6,9,6,6,3,2)=4.\]

呐,先处理5再处理非5,整个过程清晰多了。

另外,因为弄完前三行就已经提取到足够的2了,所以后面的都不用再提,直接算尾数,计算也简单了。
1

评分人数

TOP

回复 13# kuing

谢谢两位!!!

TOP

发网友的解答:

$[\frac{2018}{5}]! \cdot 2^{[\frac{2018}{5}]} \cdot [2018 \mod 5]! = 403! \cdot 2^{403} \cdot 3!$
$[\frac{403}{5}]! \cdot 2^{[\frac{403}{5}]} \cdot [403 \mod 5]! = 80! \cdot 2^{80} \cdot 3!$
$[\frac{80}{5}]! \cdot 2^{[\frac{80}{5}]} \cdot [80 \mod 5]! = 16! \cdot 2^{16} \cdot 0!$
$[\frac{16}{5}]! \cdot 2^{[\frac{16}{5}]} \cdot [16 \mod 5]! = 3! \cdot 2^{3} \cdot 1!$

所求即$(2^{403} \cdot 3!)(2^{80} \cdot 3!)(2^{16} \cdot 0!)(3! \cdot 2^3 \cdot 1!) \pmod{10} \equiv 2^{502} \cdot 6^3 \pmod{10} \equiv 4 \cdot 6 \pmod{10} \equiv 4 \pmod{10}$

TOP

楼上网友的解法暂时看不懂,倒是看懂了 isee 在 4# 给的那个链接的这个解答:

QQ截图20180617164005.png
2018-6-17 16:51


不过我也看了一段时间才看懂了,主要是卡在最长的那行的那个式子,下面按我的理解来说一下怎么来的。

那边是2016,这里换成了2018,也是一样的。

因为 `\lfloor2018/5\rfloor=403`, `\lfloor2018/5^2\rfloor=80`, `\lfloor2018/5^3\rfloor=16`, `\lfloor2018/5^4\rfloor=3`, `403+80+16+3=502`,所以 `2018!` 后面有 `502` 个零,设 `n=2018!/10^{502}`,问题即求 `n` 的个位数,由于 `2` 比 `5` 多,所以 `n` 一定是偶数。

类似于 9# 那样,对 `2018!` 提取所有的 `5`,有
\begin{align*}
\frac{2018!}{5^{502}}={}&1\times2\times3\times4\times6\times7\times8\times9\times11\times12\times\cdots \times2018\times{}\\
&1\times2\times3\times4\times6\times7\times8\times9\times11\times12\times\cdots \times403\times{}\\
&1\times2\times3\times4\times6\times7\times8\times9\times11\times12\times\cdots \times79\times{}\\
&1\times2\times3\times4\times6\times7\times8\times9\times11\times12\times\cdots \times16\times{}\\
&1\times2\times3
\end{align*}模 `5` 得\begin{align*}
\frac{2018!}{5^{502}}\equiv {}
&1\times2\times3\times4\times1\times2\times3\times4\times1\times2\times\cdots \times3\times{}\\
&1\times2\times3\times4\times1\times2\times3\times4\times1\times2\times\cdots \times3\times{}\\
&1\times2\times3\times4\times1\times2\times3\times4\times1\times2\times\cdots \times4\times{}\\
&1\times2\times3\times4\times1\times2\times3\times4\times1\times2\times\cdots \times1\times{}\\
&1\times2\times3
\pmod5,
\end{align*}即\begin{align*}
\frac{2018!}{5^{502}}\equiv{}
&(1\times2\times3\times4)^{403}\times1\times2\times3\times{}\\
&(1\times2\times3\times4)^{80}\times1\times2\times3\times{}\\
&(1\times2\times3\times4)^{16}\times{}\\
&(1\times2\times3\times4)^{3}\times1\times{}\\
&1\times2\times3
\pmod5,
\end{align*}即\[\frac{2018!}{5^{502}}\equiv (2\times3\times4)^{502}(2\times3)^3 \pmod5,\]因为 `2\times3\equiv1\pmod5`,所以\[\frac{2018!}{5^{502}}\equiv 4^{502}\pmod5,\]所以\[n\equiv 2^{502}\equiv 4\pmod5,\]由此可知 `n` 的个位为 `4` 或 `9`,但 `n` 是偶数,所以只能是 `4`。(所以最后其实并不需要用到中国剩余定理)
1

评分人数

$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 16# kuing

最后再 mod 10 显得专业啊,,,,,

TOP

回复 16# kuing

续:直观看起来就是这样:
QQ截图20180617172305.png
2018-6-17 17:50


这样的话,应该能一般地写成:设 `N\geqslant2`,作如下计算
\begin{alignat*}{2}
N\div5&=k_1&&\cdots r_1,\\
k_1\div5&=k_2&&\cdots r_2,\\
&\vdots\\
k_m\div5&=0&&\cdots r_m,
\end{alignat*}
令 `k=k_1+k_2+\cdots+k_m`,则
\[\frac{N!}{5^k}\equiv (1\times2\times3\times4)^kr_1!r_2!\cdots r_m!\pmod5,\]
令 `k\mod4=t`,则
\[\frac{N!}{10^k}\equiv 2^kr_1!r_2!\cdots r_m!\equiv 2^tr_1!r_2!\cdots r_m!\pmod5.\quad(*)\]

(1)如果 `t=0` 且 `r_1!r_2!\cdots r_m!=1`,则式 (*) 右边为 `1`,此时 `N!/10^k\equiv6\pmod{10}`;

(2)除了(1)这种特殊情况以外,式 (*) 右边都一定是偶数,此时
\[\frac{N!}{10^k}\equiv 2^tr_1!r_2!\cdots r_m!\pmod{10}.\]

咦?怎么看起来和 15# 有点像?或许就是相同的东东哩……

例1:求 `6666!` 的最后一个非零数字。
:有\begin{alignat*}{2}
6666\div5&=1333&&\cdots 1,\\
1333\div5&=266&&\cdots 3,\\
266\div5&=53&&\cdots 1,\\
53\div5&=10&&\cdots 3,\\
10\div5&=2&&\cdots 0,\\
2\div5&=0&&\cdots 2,
\end{alignat*}根据上述结论,有 `k=1333+266+53+10+2=1664`, `t=0`,即 `6666!` 末尾有 `1664` 个零,且\[\frac{6666!}{10^{1664}}\equiv 2^01!3!1!3!0!2!=72\pmod{10},\]所以最后一个非零数字是 `2`。

例2:求 `130!` 的最后一个非零数字。
:有\begin{alignat*}{2}
130\div5&=26&&\cdots 0,\\
26\div5&=5&&\cdots 1,\\
5\div5&=1&&\cdots 0,\\
1\div5&=0&&\cdots 1,
\end{alignat*}根据上述结论,有 `k=26+5+1=32`, `t=0`,且恰好余数都不超过 `1`,属于情况(1),所以最后一个非零数字是 `6`。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 18# kuing


你再研究会,就把这问题完全解决了
你要是去看看初等数论相关章节,那还了得~,直接成专家

TOP

回复 19# isee

俺数论是渣渣了……以前也学过一会,根本木有赶脚……

TOP

返回列表 回复 发帖