阶乘的最后一位非零位

张文泰 posted @ 2010年1月12日 03:42 in Art of Science with tags 数论 , 7929 阅读

阶乘的最后一位非零位就是n!的数值中从右到左第一个非零的数字。比如,7!=5040,那么7!的最后一位非零位就是4。一个粗略的想法是每10个数字的末尾数相乘是一个定植,那么n个连续的自然数也可以类似地转化,接着就可以求出。这个想法无疑是错误的,因为注意到2*5=10,而12*15=180,两个结果的末位非零数并不相等,所以末尾数相乘不是10个数字为一个循环。

如果要求n!末尾0的个数,就是一个非常简单的问题。因为10=2*5,我们只要求出2和5在n!的标准分解式中出现了多少次,就可以求出末尾0的个数。而又由于2出现的次数一定比5多,所以,只需要求出5出现的次数。例如,n=2005,那么5出现的次数就是401+80+16+3=500个,也就是2005!的末尾有500个0。

现在我们对n!的情况有了一个大概的认识。简单点来说,n!=2a5bc,这里c是所有不包含2和5的因数的乘积。显然,最后一位非零位取决于2a-bc的最后一位。我们只要想办法求出c,n!的非零位就很容易了。注意到如果一个数字的末位如果是3,5,7,9,那么一定是c的组成部分。但是这些数字还不够,因为当2和5被提取之后,又产生了新的末位为3,5,7,9的数字,所以我们要逐次的提取2和5这两个因数,然后算出每种情况下末位为3,5,7,9的数字的数量。

回忆求2这个因数的办法,就是逐次的除以2来缩小规模。例如,当n=2005时,只含有一个因数2的数一共有1002个,含有两个因数2的数字一共有501个,……。也就是一种递归的思想,不过这里是尾递归,可以消除。下面关于如何求出末位为3,5,7,9的数字的方法就不再赘述了,直接给出代码,相信还是能够理解的。

//co2,co3,co5,co7,co9分别表示了2,3,5,7,9的个数。
static int co2,co3,co5,co7,co9;

void calc(int n) {
  if (n<=1) return;
  for (int i = n; i>0; i /= 5) {
    int p = i/10,q = i%10;
    co3 = p+(int)(q>=3);
    co5 = p+(int)(q>=5);
    co7 = p+(int)(q>=7);
    co9 = p+(int)(q>=9);
  }
  co2 += n/2;
  calc(n/2);
}

至此,问题转化为了2,3,5,7,9之间幂的关系,注意到32n=9n,而$3^n\equiv 7^{3n}\pmod{10}$,所以又可以转化为3的幂,下面的过程就简单多了。

其实求n!的最后一位非零位还有其它的方法,但其实也不外乎利用递归的思想提取因数,来达到化大为小的目的。有兴趣的可以去Google一下,可以找到很多资料。


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License
Avatar_small
pfermat 说:
2010年1月12日 16:59

看到最新文章路过 =w=
2x5=10, 12x15=180,其实楼主想说模100的吧
另外考虑到10!的最后一位非零数字是8,实际上每十个数字确实可以看成8,4,2,6,这是8的方幂的循环部分。进一步,我们可以计算一下,当n同余0、1、2、3、4以及9(模10)的时候,最后一位非零数字都可以用以上的方法直接乘出来,而当n同余5的时候,由于最后一位变成了零,就必须向高一位寻求结果。
此外,初等数论中有n!的分解式,我觉得可以直接拿来用,不过需要一张素数表。

Avatar_small
Wentai ZHANG 说:
2010年1月12日 19:28

@pfermat: 昨天简单地看了一下您的blog,觉得这个主题的背景有点囧。
那个地方确实写错了,我等下改。实际上求n!末位数的关键在于排除2和5的干扰,您说“每十个数字确实可以看成8,4,2,6”,但是我验证发现30!的末位数为8,不知道我是不是理解错了。
初等数论里面那个n!的分解式在这里不好直接用,要用递归的方法求的,原因是都是简单素因数,不用考虑比较复杂的情况。

Avatar_small
pfermat 说:
2010年1月13日 01:04

@Wentai ZHANG: 想了下我的说法确实有问题……
背景什么的,咱是控二次元的 XD

Avatar_small
Wentai ZHANG 说:
2010年1月13日 01:19

@pfermat: 我控2.5次元……不过这个背景确实很囧,而且不能设置,比起您的头像差远了。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter