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

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


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


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

TOP

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}}

TOP

回复 21# isee

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

TOP

回复 22# isee

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

TOP

QQ截图20180617185112.jpg
2018-6-17 18:52

TOP

回复 25# lemondian

难得看到柠檬出手解个题

TOP

我说我好像见过,所以我知道我不会
http://kuing.orzweb.net/viewthread.php?tid=4167

TOP

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

TOP

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

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

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

TOP

本帖最后由 乌贼 于 2018-6-18 18:05 编辑

所有尾数是$ 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 $?

TOP

回复 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!)$。

TOP

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

TOP

本帖最后由 业余的业余 于 2019-3-12 00:28 编辑

注意到 $\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$

TOP

注意到 $\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

TOP

本帖最后由 业余的业余 于 2019-3-13 02:18 编辑

回复 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$, 都是正确的。 算法比较繁琐,但有较大可能是正确的。
  1. unsigned V(unsigned n)
  2. {
  3.         unsigned v=1;
  4.         n%=20;
  5.         if(n>=10)
  6.         {
  7.                 v=9;
  8.                 n-=10;
  9.         }
  10.         return (v*(n<=2?1:n<=6?3:n<=8?1:9))%10;
  11. }


  12. unsigned U(unsigned n)
  13. {
  14.         unsigned v=1;
  15.         if(n<=2) return 1;
  16.         v*=V(n);
  17.         for(int j=n/5; j>0; j/=5)
  18.         {
  19.                 v*=V(j);
  20.                 v%=10;
  21.         }
  22.         return (v*U(n/2))%10;
  23. }
复制代码

TOP

返回列表 回复 发帖