繁體
|
簡體
Sclub交友聊天~加入聊天室當版主
(檢舉)
分享
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
标题:
[数论]
$n!$ 最后一位数字加强版
[打印本页]
作者:
业余的业余
时间:
2019-3-13 07:54
标题:
$n!$ 最后一位数字加强版
1. $2019!$ 去掉尾部所有 $0$ 后的最后两位数字。模 $25$ 怎么操作?
2. $2019!$ 转换为 $30$ 进制,去掉尾部的所有 $0$ 后,个位数字的十进制表达。加了一个新的质因子 $3$.
作者:
业余的业余
时间:
2019-3-13 20:56
本帖最后由 业余的业余 于 2019-3-13 23:47 编辑
回复
1#
业余的业余
繁琐无趣,乏人问津,自己试试吧。
设 $2019!$ 后有 $k$ 个零,记 $\cfrac {2019!}{10^k}=n, \cfrac {2019!}{5^k}=m$, 显然 $n,m\equiv 0 \pmod{4}, n,m \text{ 与 } 5 \text{互质}$,现在求 $m$ 除 $25$ 的余数。
辅助表
数 商 余
2019 80 19
403 16 3
80 3 5
16 0 16
3 0 3
$k=403+80+16+3=502$
记 $\displaystyle a_k=\prod_{i=1}^{k, i \text{不是} 5 \text{ 的倍数}} i$,有
$\displaystyle a_{24}\equiv \prod_{i=1}^{12, \text{非 5 倍数 }} -i^2\equiv (2\cdot 3 \cdot 4 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 11 \cdot 12)^2\equiv( 7 \cdot 9 \cdot 11)^2\equiv -1 \pmod{25}$
$\displaystyle a_{19}\equiv \cfrac {a_{24}}{-4\cdot -3 \cdot -2 \cdot -1}\equiv 1 \pmod{25}$
$\displaystyle a_3\equiv 6 \pmod{25}$
$\displaystyle a_5\equiv a_4\equiv -1 \pmod{25}$
$\displaystyle a_{16}\equiv \cfrac {a_{19}}{-8\cdot -7 \cdot -6}\equiv \cfrac 1{14} \equiv 9 \pmod{25}$
于是
$m\equiv (-1)^{80}(1)\cdot (-1)^{16}(6)\cdot (-1)^3(-1)\cdot(9)\cdot(6)\equiv -1\pmod{25} $
$n\equiv \cfrac {m}{2^{502}}\equiv \cfrac {-1}{(2^{20})^{25}\cdot 4}\equiv \cfrac {-1}4\equiv 6 \pmod{25}$
注: $\varphi(25)=5^2-5=20, \gcd(25,2)=1 \implies 2^{20}\equiv 1 \pmod{25}$
显然,最后两位是 $56$. (除 $25$ 余 $6$, 且能被 $4$ 整除的,最后两位必为 $56$).
作者:
业余的业余
时间:
2019-3-13 22:10
本帖最后由 业余的业余 于 2019-3-14 00:40 编辑
第 2 题 令 $k$ 为 $2019!$ 三十进制表示数的尾部的 $0$ 的个数。 记 $n=\cfrac {2019!}{30^k},m=\cfrac{2019!}{5^k}$, 显然 $m,n$ 是 $6$ 的倍数,且与 $5$ 互质。
从前步知 $m\equiv 24 \pmod{25}$, 显然有 $m\equiv 4 \pmod{5}$.
$n\equiv \cfrac m{2^{502}3^{502}}\equiv \cfrac 4{4\cdot 4}\equiv 4 \pmod{5}$
注: $\varphi(5)=4, \therefore 2^4\equiv 3^4\equiv 1 \pmod{5}$
满足:
0. 是 $6$ 的倍数;
1. 是 $1-29$ 的整数;
2. 除 $5$ 余 $4$
的整数 $24$ 就是所求尾数。
作者:
realnumber
时间:
2019-3-14 13:52
56,24 对的,程序检验了下
var
k,m,n,s,t:longint;
begin
n:=1;
for m:=1 to 2019 do
begin
n:=n*m;
for k:=1 to 5 do if ((n mod 30)=0) then n:=(n div 30);
n:=n mod 810000;
end;
writeln(n);
end.
作者:
业余的业余
时间:
2019-3-14 22:29
回复
4#
realnumber
后来注意到基础数论上的两个定理能一定程度上减少这类问题的计算量。一个是
1. $p$ 是 质数 $\iff (p-1)!\equiv -1 \pmod{p}$
所以 $4! \equiv -1 \pmod{5}, 6!\equiv -1 \pmod{7}$.
2. 如果 $\gcd(n,m)=1$, 那么 $m^{\varphi(n)}\equiv 1 \pmod{n}$, 其中 $\varphi(n)$ 是 欧拉-$\varphi$ 函数,表示不大于 $n$ 的正整数中与 $n$ 的最大公约数为 $1$ 的数的个数。显然对质数 $p$ 有 $\varphi(p)=p-1$.
作者:
业余的业余
时间:
2019-3-15 01:12
本帖最后由 业余的业余 于 2019-3-15 01:15 编辑
这个问题再往更大点的质数处玩,最好掌握 扩展欧几里得算法。这个算法以前看过,也貌似看懂过,但不怎么用,每次差不多都是从头理解。这里做个笔记。
$\gcd(a,b)=g$, 求 $x,y\in \mathbb{Z}$, 满足 $ax+by=g$. 这个问题的解有着比较广泛的应用。扩展欧几里得算法可用于解决这类问题。我个人觉得用向量的方式最易于理解。
1. 求 $130x+61y=1$ 的一个整数解
$\begin {align*}
8&=130-2\cdot 61=(1,-2)\cdot (130,61)\\
5&=61-7\cdot 8= [(0,1)-7(1,-2)]\cdot (130,61)=(-7,15)\cdot(130,61)\\
1&=61-12\times 5=[(0,1)-12(-7,15)]\cdot(130,61)=(84,-179)\cdot(130,61)
\end{align*}$
$\therefore x=84, y=-179$ 是原方程的一个整数解。这里并不是严格意义上的扩展欧几里得算法。
2. 求 $17x \equiv 1 \pmod{ 61}$
解: 即求 $17x+61y=1$ 的一个整数解中的 $x$. 这个也是所谓的 inverse modulo $n$ 问题。
$
\begin{align*}
10&=61-3\cdot 17=(1,-3)\cdot (61,17) \hspace{1cm} \text{ 以下省略后面的向量及点积运算}\\
1&=61-6\times 10=(1,0)-6(1,-3)=(-5,18)
\end{align*}$
$18$ 即所求的 $x$。
作者:
业余的业余
时间:
2019-3-15 01:56
本帖最后由 业余的业余 于 2019-3-16 00:57 编辑
求 $2019!$ 的 $455(=5\times 7 \times 13)$ 进制表示数去掉尾部零后的个位数的十进制表示数。和主贴问题 $2$ 完全一样的处理。运用上面的一些技巧可使计算量尽可能的小,小到笔算可轻易解决。
辅助表 (除 13)
数 商 余
2019 155 4
155 11 12
11 0 11
和 166
用类似的方法定义 $a_k$, 以下说不通的地方都是省略了模 13。 $a_{12}\equiv -1, a_{11}\equiv 1, a_4\equiv -2$
记 $m=\cfrac {2019!}{13^{166}}$, 则 $m\equiv (-1)^{166}a_4a_{12}a_{11}\equiv (-2)(-1)(1)\equiv 2 \pmod{13}$
于是 $\cfrac m{5^{166}7^{166}}\equiv \cfrac 2{35^{10}}\equiv \cfrac 2{(-4)^{10}}\equiv \cfrac 1{2^{19}} \equiv \cfrac 1{2^7} \pmod{13}$
上面利用了 $\varphi(13)=12, 5^{12}\equiv 7^{12}\equiv 2^{12}\equiv 1 \pmod{13}$
$2^7=128$, 如果有一定的编程经验,这个应该是印在脑子里的了。问题变成了求 $128$ 的 inverse modulo 13, 可以用上面的扩展欧几里得算法求解,即求 $128 x +13y=1$ 的整数解中的 $x$
$\begin{align*}
11&=128-9\times 13=(1,-9)\\
2&=13-11=(0,1)-(1,-9)=(-1,10)\\
1&=11-5\times 2=(1,-9)-5(-1,10)=(6,-59)
\end{align*}$
$6$ 是所求的 $x$. 我曾经想硬抗,发现数字大了还是用普遍接受的算法来得快、稳、准。
(注。以上略笨, $\cfrac 1{128}\equiv \cfrac 1{-2}\equiv \cfrac 1{11} \pmod{13}$, 答案当然仍然是 $6$, 数字小多了
)
于是,所求的数
1. 除 $13$ 余 $6$,
2. 在 $1$ 到 $454$ 之间的整数
3. 是 $5\times 7=35$ 的倍数。
即 $35x\equiv 6 \pmod{13}$, 或 $35x+13y=6$ 又是一个扩展欧几里得算法问题,不嫌啰嗦的话,把草稿纸上的内容再罗列一遍:
如果有 $35x+13y=1$ 的话,显然 $x'=6x,y'=6y$ 是原方程的解.
$\begin{align*}
4&=-35+3\times 13=(-1,3)\\
1&=9\times 4 -35=9(-1,3)-(1,0)=(-10,27)
\end{align*}$
所以 $-10$ 是新方程的解, $-60$ 是原方程的解,$-60\equiv 5\pmod{13}$, $35\times 5=175$ 是所求的答案。检验 $175\equiv 6\pmod{13}$
欢迎光临 悠闲数学娱乐论坛(第2版) (http://kuing.orzweb.net/)
Powered by Discuz! 7.2