求 2018! 的最后一个非零数字．

isee

回复  kuing

续：直观看起来就是这样：


这样的话，应该能一般地写成：
\begin{alignat*}{2}
N\div5&=k_ ...
kuing 发表于 2018-6-17 17:51

这搞法，是不是就是分解因式$n!$哦。。。

isee

MMC分解的结果：

{{2, 2011}, {3, 1004}, {5, 502}, {7, 334}, {11, 200}, {13, 166}, {17, 124}, {19, 111}, {23, 90}, {29, 71}, {31, 67}, {37, 55}, {41, 50}, {43, 47}, {47, 42}, {53, 38}, {59, 34}, {61, 33}, {67, 30}, {71, 28}, {73, 27}, {79, 25}, {83, 24}, {89, 22}, {97, 20}, {101, 19}, {103, 19}, {107, 18}, {109, 18}, {113, 17}, {127, 15}, {131, 15}, {137, 14}, {139, 14}, {149, 13}, {151, 13}, {157, 12}, {163, 12}, {167, 12}, {173, 11}, {179, 11}, {181, 11}, {191, 10}, {193, 10}, {197, 10}, {199, 10}, {211, 9}, {223, 9}, {227, 8}, {229, 8}, {233, 8}, {239, 8}, {241, 8}, {251, 8}, {257, 7}, {263, 7}, {269, 7}, {271, 7}, {277, 7}, {281, 7}, {283, 7}, {293, 6}, {307, 6}, {311, 6}, {313, 6}, {317, 6}, {331, 6}, {337, 5}, {347, 5}, {349, 5}, {353, 5}, {359, 5}, {367, 5}, {373, 5}, {379, 5}, {383, 5}, {389, 5}, {397, 5}, {401, 5}, {409, 4}, {419, 4}, {421, 4}, {431, 4}, {433, 4}, {439, 4}, {443, 4}, {449, 4}, {457, 4}, {461, 4}, {463, 4}, {467, 4}, {479, 4}, {487, 4}, {491, 4}, {499, 4}, {503, 4}, {509, 3}, {521, 3}, {523, 3}, {541, 3}, {547, 3}, {557, 3}, {563, 3}, {569, 3}, {571, 3}, {577, 3}, {587, 3}, {593, 3}, {599, 3}, {601, 3}, {607, 3}, {613, 3}, {617, 3}, {619, 3}, {631, 3}, {641, 3}, {643, 3}, {647, 3}, {653, 3}, {659, 3}, {661, 3}, {673, 2}, {677, 2}, {683, 2}, {691, 2}, {701, 2}, {709, 2}, {719, 2}, {727, 2}, {733, 2}, {739, 2}, {743, 2}, {751, 2}, {757, 2}, {761, 2}, {769, 2}, {773, 2}, {787, 2}, {797, 2}, {809, 2}, {811, 2}, {821, 2}, {823, 2}, {827, 2}, {829, 2}, {839, 2}, {853, 2}, {857, 2}, {859, 2}, {863, 2}, {877, 2}, {881, 2}, {883, 2}, {887, 2}, {907, 2}, {911, 2}, {919, 2}, {929, 2}, {937, 2}, {941, 2}, {947, 2}, {953, 2}, {967, 2}, {971, 2}, {977, 2}, {983, 2}, {991, 2}, {997, 2}, {1009, 2}, {1013, 1}, {1019, 1}, {1021, 1}, {1031, 1}, {1033, 1}, {1039, 1}, {1049, 1}, {1051, 1}, {1061, 1}, {1063, 1}, {1069, 1}, {1087, 1}, {1091, 1}, {1093, 1}, {1097, 1}, {1103, 1}, {1109, 1}, {1117, 1}, {1123, 1}, {1129, 1}, {1151, 1}, {1153, 1}, {1163, 1}, {1171, 1}, {1181, 1}, {1187, 1}, {1193, 1}, {1201, 1}, {1213, 1}, {1217, 1}, {1223, 1}, {1229, 1}, {1231, 1}, {1237, 1}, {1249, 1}, {1259, 1}, {1277, 1}, {1279, 1}, {1283, 1}, {1289, 1}, {1291, 1}, {1297, 1}, {1301, 1}, {1303, 1}, {1307, 1}, {1319, 1}, {1321, 1}, {1327, 1}, {1361, 1}, {1367, 1}, {1373, 1}, {1381, 1}, {1399, 1}, {1409, 1}, {1423, 1}, {1427, 1}, {1429, 1}, {1433, 1}, {1439, 1}, {1447, 1}, {1451, 1}, {1453, 1}, {1459, 1}, {1471, 1}, {1481, 1}, {1483, 1}, {1487, 1}, {1489, 1}, {1493, 1}, {1499, 1}, {1511, 1}, {1523, 1}, {1531, 1}, {1543, 1}, {1549, 1}, {1553, 1}, {1559, 1}, {1567, 1}, {1571, 1}, {1579, 1}, {1583, 1}, {1597, 1}, {1601, 1}, {1607, 1}, {1609, 1}, {1613, 1}, {1619, 1}, {1621, 1}, {1627, 1}, {1637, 1}, {1657, 1}, {1663, 1}, {1667, 1}, {1669, 1}, {1693, 1}, {1697, 1}, {1699, 1}, {1709, 1}, {1721, 1}, {1723, 1}, {1733, 1}, {1741, 1}, {1747, 1}, {1753, 1}, {1759, 1}, {1777, 1}, {1783, 1}, {1787, 1}, {1789, 1}, {1801, 1}, {1811, 1}, {1823, 1}, {1831, 1}, {1847, 1}, {1861, 1}, {1867, 1}, {1871, 1}, {1873, 1}, {1877, 1}, {1879, 1}, {1889, 1}, {1901, 1}, {1907, 1}, {1913, 1}, {1931, 1}, {1933, 1}, {1949, 1}, {1951, 1}, {1973, 1}, {1979, 1}, {1987, 1}, {1993, 1}, {1997, 1}, {1999, 1}, {2003, 1}, {2011, 1}, {2017, 1}}

kuing

回复 21# isee

不是，从头到尾都只是在处理和5有关的东西，其他是不用分的

isee

回复 22# isee

这质数判断比较难，应该不通。。

lemondian

isee

回复 25# lemondian

难得看到柠檬出手解个题

isee

我说我好像见过，所以我知道我不会
kuing.cjhb.site/forum.php?mod=viewthread&tid=4167

realnumber

果然，还是以前碰到过的.

kuing

修改了一下18#，顺便加了栗子……

回复 26# isee
那个排版他应该排不出来，一定是转的……

回复 27# isee
那帖我一点印象也木有，当年应该是一看数论就直接略过了，不过今天我竟然弄懂了，你是不是也应该想办法弄懂它……

乌贼

所有尾数是$ 9 $的乘积（201个）尾数为$ 9 $，
所有尾数是$ 8 $的乘积（202个）尾数为$ 4 $，
所有尾数是$ 7 $的乘积（202个）尾数为$ 9 $，
所有尾数是$ 6 $的乘积（202个）（抽出$ 48$个$ 2^{48} $，提取的数的十位数为偶数 ）后的尾数为$ 6 $，
除$ 4 $外所有尾数是$ 4 $的乘积（201个）尾数为$ 4 $，
所有尾数是$ 3 $的乘积（202个）尾数为$ 9 $，
所有尾数是$ 0 $的乘积（201个）的非零尾数为$ 8 $
当尾数为$ 5 $时\[  5^{202}\times (1\times 3\times 5\times 7\times 9\times 11\cdots \times 401\times 403 )\\=5^{242}\times (1\times 3\times 5\times 7\times 9\times \cdots \times 77\times 79)\times (1\times3\times 7\times 9\times \cdots 401\times 403 )\\5^{250}\times (1\times 3\times 5\times 7\times \cdots \times 15)(1\times 3\times 7\times 9\times \cdots \times 77\times 79)(1\times 3\times 7\times 9\times \cdots \times 401\times 403) \]有$ 4\times (1\times 3\times 5\times 9\times \cdots \times 15) $的非零尾数为$ 1 $，$  1\times 3\times 7\times 9\times \cdots \times 77\times 79$的尾数为$ 1 $，$ 1\times 3\times 7\times 9\times \cdots \times 401\times 403) $的尾数为$ 3 $。
所以\[  4\times (1\times 3\times 5\times 9\times \cdots \times 15)(1\times 3\times 7\times 9\times \cdots \times 77\times 79)(1\times 3\times 7\times 9\times \cdots \times 401\times 403)  \]的尾数为$ 3 $
当尾数为$ 2 $时\[ 2^{202}\times (1\times 6\times 11\times 16\times 21\times 26\times \cdots \times 1006) \]有\[ 1\times 6\times 11\times 16\times 21\times 26\times \cdots \times 1006) \]的尾数为$ 6 $
综上$ 2018! $的最后一个非零数字是\[ 9\times 4\times 9\times 6\times 4\times 9\times 8\times 3\times 6 \]的尾数即$ 6 $？

abababa

回复 15# abababa

发一下网友的证明：
设$f(n!)$表示$n!$最末位的非零数字。设$[x]$为不超过$x$的最大整数。显然
\[n! = (5 \cdot 10 \cdot 15 \cdots 5[\frac{n}{5}]) \cdot (1 \cdot 2 \cdot 3 \cdot 4)(6 \cdot 7 \cdot 8 \cdot 9) \cdots = (5^{[\frac{n}{5}]} \cdot [\frac{n}{5}]!) \cdot (1 \cdot 2 \cdot 3 \cdot 4)(6 \cdot 7 \cdot 8 \cdot 9) \cdots\]

注意四数一组的分组，可以从大数到小数排序（例如$103!$，分组可以为$(103 \cdot 102 \cdot 101 \cdot 99)(98 \cdot 97 \cdot 96 \cdot 94) \cdots (3 \cdot 2 \cdot 1)$，最末一个分组即为$(n \bmod 5)!$）。对于不是$5$的倍数的每组数，都有$(5k+1)(5k+2)(5k+3)(5k+4) \equiv 4 \pmod{10}$

因此分组部分可写为$(10b_1+4)(10b_2+4) \cdots (10b_{[\frac{n}{5}]}+4)$。而
\[(10b_1+4)(10b_2+4) \cdots (10b_{[\frac{n}{5}]}+4) = 2^{[\frac{n}{5}]}(5b_1+2)(5b_2+2)\cdots(5b_{[\frac{n}{5}]}+2)\]

将$(5b_1+2)(5b_2+2)\cdots(5b_{[\frac{n}{5}]}+2)$展开可知$(5b_1+2)(5b_2+2)\cdots(5b_{[\frac{n}{5}]}+2) \equiv 2^{[\frac{n}{5}]} \pmod{10}$，所以
\[(10b_1+4)(10b_2+4) \cdots (10b_{[\frac{n}{5}]}+4) \equiv 2^{[\frac{n}{5}]} \cdot 2^{[\frac{n}{5}]} \pmod{10}\]

因此
\[f(n!) = f(5^{[\frac{n}{5}]} \cdot [\frac{n}{5}]! \cdot 2^{[\frac{n}{5}]} \cdot 2^{[\frac{n}{5}]} \cdot (n \bmod 5)!) = f([\frac{n}{5}]! \cdot 2^{[\frac{n}{5}]} \cdot (n \bmod 5)!)\]

注意$f(x! \cdot 2^{y} \cdot (n \bmod 5)!) = f(x!)f(2^{y})f(n \bmod 5)$，于是有
\[f(n!) = f([\frac{n}{5}]!) \cdot f(2^{[\frac{n}{5}]}) \cdot f((n \bmod 5)!)\]

递推即能算$f(n!)$。

青青子衿

回复 31# abababa
这个分组展开的方法也不错

业余的业余

注意到 $\displaystyle \prod_{i=1}^{10} i  \equiv \prod_{i=11}^{20} i\equiv \cdots \equiv \prod_{i=1001}^{1010} i\equiv \prod_{i=k}^{k+9} i(k\in\mathbb{N})\equiv 3\cdot 4 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \equiv 8 (\text{模10 前截头后去尾运算})$

又 $\displaystyle \prod_{i=1}^{8} i\equiv 2 ( \text{模10前截头后去尾运算})$

所求 $\equiv 2\cdot 8^{201}\equiv 2^{604}\equiv 2^{151\times 4} \pmod{10}$

而 $2^{4k} \equiv 6 \pmod{10}, k\in \mathbb{Z}$

故所求值为 $6$

kuing

注意到 $\displaystyle \prod_{i=1}^{10} i  \equiv \prod_{i=11}^{20} i\equiv \cdots \equiv \prod_{i=1001}^{1010} i\equiv \prod_{i=k}^{k+9} i(k\in\mathbb{N})\equiv 3\cdot 4 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \equiv 8 (\text{模10 前截头后去尾运算})$ ...
业余的业余 发表于 2019-3-11 23:56

21*22*...*30 的尾数就不是 8

业余的业余

回复 34# kuing

11 到 20 就不行， 20 多贡献了个 2.  我再仔细想想看有没有补救的办法。

除特别说明，以下都指去掉因子 $2,5$ 后的个位数。

记 $n!$ 去掉所有的 $2,5$两个因子后的个位数为 $U(n)$. 记 不大于 $n$ 的个位数为 $\{1,3,7,9\}$ 之一的所有正整数的连乘积的个位数为 $V(n)$.

把 $\{1,2,\cdots, n\}$ 中的数分为三组 ：$2$ 的倍数，$5$ 的倍数， 其它。显然，其它组对个位数的贡献为 $V(n)$

$2$ 的倍数组每个数提出公因数 $2$ 后，刚好为 $\{1,2,\cdots,\lfloor{\cfrac n2}\rfloor\}$, 该组对尾数的贡献为  $U(\lfloor{\cfrac n2\}\rfloor})$. 这个可以递归地求解。

$5$ 的奇数倍组每个提出公因数 $5$ 后，为 $\{1,3,(1\times 5),7,9,11,13,(3\times 5)...\}$, 该组对尾数的贡献为 $V(\lfloor{\cfrac n5}\rfloor)V(\lfloor{\cfrac n{25}}\rfloor)V(\lfloor{\cfrac n{125}}\rfloor)\cdots $.

关于 $V(n)$ 有如下事实， $V(20k)=1, V(10(2k+1))=9$.

于是 $U(2018)=V(2018)U(1009)V(403)V(80)V(16)V(3)=7U(1009)$ (模10意义上， 下同)

$U(1009)=V(1009)U(504)V(201)V(40)V(8)V(1)=9U(504), U(2018)=3U(504)$

$U(504)=V(504)U(252)V(100)V(20)V(4)=9U(252), U(2018)=7U(252)$

$U(252)=U(126)V(252)V(50)V(10)V(2)=9U(126), U(2018)=9U(126)$

$U(126)=U(63)V(126)V(25)V(5)(V1)=3U(63), U(2018)=7U(63)$

$U(63)=U(31)V(63)V(12)V(2)=3U(31), U(2018)=3U(31)$

$U(31)=U(15)V(31)V(6)V(1)=7U(15), U(2018)=U(15)$

$U(15)=U(7)V(15)V(3)=U(7), U(2018)=U(7)$

$U(7)=U(3)V(7)V(1)=U(3), U(2018)=U(3)$

$U(3)=3, U(2018)=3$

上面的过程有错误，但程序验证得到了 $U(2018)=7,U(2016)=9$, 都是正确的。 算法比较繁琐，但有较大可能是正确的。

2. unsigned V(unsigned n)
3. {
4.         unsigned v=1;
5.         n%=20;
6.         if(n>=10)
7.         {
8.                 v=9;
9.                 n-=10;
10.         }
11.         return (v*(n<=2?1:n<=6?3:n<=8?1:9))%10;
12. }
15. unsigned U(unsigned n)
16. {
17.         unsigned v=1;
18.         if(n<=2) return 1;
19.         v*=V(n);
20.         for(int j=n/5; j>0; j/=5)
21.         {
22.                 v*=V(j);
23.                 v%=10;
24.         }
25.         return (v*U(n/2))%10;
26. }

复制代码