找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 842|回复: 0
收起左侧

[资源分享] 8: Find Last Non-Zero Digit of Factorial

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-4-2015 09:53 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

推公式 + 找规律,可以参考一篇讲的很细致的博文:http://www.cnblogs.com/LETTers/archive/2012/04/18/2456089.html
  1. // reference to http://www.cnblogs.com/LETTers/archive/2012/04/18/2456089.html
  2. int lastDigit(int n)
  3. {
  4.         // kMeta【i】 = last non zero digit of i!
  5.         static const int kMeta[10] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
  6.         // g(i) = replace multiples of 5 by 1 in i!, we get periodical last digit
  7.         // g(m*10+n) % 10 = kMod5[n]
  8.         static const int kMod5[10] = {6, 6, 2, 6, 4, 4, 4, 8, 4, 6};
  9.         // to pair those 5, we need to div 2, which is also periodical as there are much more 2 than 5
  10.         static const int kDiv2[10] = {0, 0, 6, 0, 2, 0, 8, 0, 4, 0};

  11.         if(n < 10) return kMeta[n];

  12.         int res = lastDigit(n/5) * 6 * kMod5[n%10] % 10;
  13.         int cnt = n/5 % 4;
  14.         while(cnt--) res = kDiv2[res];
  15.         return res;
  16. }
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表