以文本方式查看主题

-  W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  求N!的最后一位非0位  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=56765)

--  作者：hitlyq
--  发布时间：12/14/2007 11:04:00 PM

--  求N!的最后一位非0位
今有一个数N,数值较大,为0~10^1000,求其阶乘的最后一非0位,输出其值
sample :
input :0
1
5
10
output:1(0!=1)
1(1!=1)
2(5!=120)
8(10!=3628800)

数值很大,应该没人直接求其阶乘再判断吧.大家给个好方法,期待中................

--  作者：njurain
--  发布时间：12/20/2007 8:07:00 PM

--  
你可以这么做：
写成：
  1   2  3   4   5   6   7   8   9   10
11 12 13 14 15 16 17 18  19 20
。。。。。
X1 X2.....

多少行很容易知道；[N/10]
然后XX0的没有影响
在看看有多少个5因子，就看5那列就可以了
然后先用8那列 并这些5（每个8=2^3）
用2那列填补可能的不足的5；
下面乘乘就是了。丢掉高位注意。

当然，你可以用数论的知识更快的做；
手算就可以了。

--  作者：homeren0215
--  发布时间：1/13/2008 9:31:00 PM

--  
令r= N mod (『N/100『 * 100)
如果 r=0, 那么最后一位非零位是8
如果 r in (1-9) 则计算s = 8 × r!,
如果 r in (1-19),则计算s = 4 * (r-10)!,
如果 r in (1-29), 则计算s = 2 *(r-20)!*2,
如果 r in (1-39)，则计算s = 6*(r-30)!*2*3,
如果 r in (1-49), 计算s = 8*(r-40)!*2*3*4,
如果r in (1-59), 计算 s = 4*(r-50)!*2*3*4*5,
....
如果r in（１－９９），则计算ｓ＝４×（ｒ－９０）！×９！
最终，Ｎ！的最后一个非零位是ｓ的最后一位非零位
--  作者：caruru331
--  发布时间：1/17/2008 1:42:00 AM

--  
楼上的方法复杂度是指数级的
--  作者：fishyuze
--  发布时间：2/2/2008 11:28:00 AM

--  
用数论做 分解质因数
--  作者：qianjigui
--  发布时间：2/16/2008 11:42:00 PM

--  
以下是引用fishyuze在2008-2-2 11:28:00的发言：
用数论做 分解质因数


这个题目好熟悉啊，好象是tju上面的。谢谢提示。
--  作者：fishyuze
--  发布时间：2/17/2008 10:28:00 AM

--  
以下是引用qianjigui在2008-2-16 23:42:00的发言：
[quote]以下是引用fishyuze在2008-2-2 11:28:00的发言：
用数论做 分解质因数
[/quote]
这个题目好熟悉啊，好象是tju上面的。谢谢提示。


嗯 poj也有 类似的~~
--  作者：xbtianlang
--  发布时间：4/16/2008 1:12:00 PM

--  
好久没写程序，只说一下大致算法：
result=1;
for(i=2;i<=n;i++)  //0,1结果为1
{ result*=i;
  while(result%10==0) result /=10;  //去末尾0
  while(result%2==1)
  { result *= 6; //末尾非0数为奇数则乘6
    while(result%10==0) result /=10;  //去末尾0
  }
  result %=10; //保留非0个位数。
}


[此贴子已经被作者于2008-4-16 16:32:26编辑过]
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 78.125ms