pku1150(经典数论,质因子)

时间:2020-11-27 00:21:37

http://162.105.81.212/JudgeOnline/problem?id=1150

题意:求C(n, m)最后一位非0位。n!/(n-m)!

此题是很经典的数论题,做完学到了很多东西,但是不是自己能做出来的;下面转帖:第四维空间博客的解析。

这个题怎么来做呢?先别急,我们先来讨论一下下面几个子问题:
1.如何求出n阶乘中质因数x(比如说5)出现的次数?
比如说15的阶乘 :1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
由于5这个质因数只在5的倍数里面才出现,所以我从5,10,15中各抽出一个5,这相当于有15/5个质因数5,之后5,10,15就变成了1,2,3;
由于非5的倍数显然不在考虑范围之内,所以我们只需继续讨论它的子问题3!即可。
这样,我们可以用递归来解决这个问题。有了这个方法,我们是不是能够轻易地解决n!末尾有多少个0呢?想想看...n!后0的个数是不是就和某个质因数的个数有关呢?^_^
比如说,我们要求5出现的次数,可以这样写:

 

 

 2.如何求出n!阶乘最后非0位?
比如说我们要找10!最后非0位,由于质因数2和5组合之后会使得末尾产生0.那么我们不妨把10!中2,5质因数全部去掉,(但是请注意2的数目其实比5的要多,所以我们要在最后考虑多余的2对末位的影响)
如 1*2*3*4*5*6*7*8*9*10 去掉2 ,5 因子后 就是1*1*3*1*1*3*7*1*9*1,由于2,5因子已经被去除,那么剩下的数字末尾一定是3,7,9,1中四者之一。然后我们再求出这么一串数相乘以后末尾的数是几.最后再补上2对末位的影响即可!

总结一下,求10!最后一个非0位的步骤如下:
step1:首先将10!中所有2,5因子去掉;
step2:然后求出剩下的一串数字相乘后末尾的那个数。
step3:由于去掉的2比5多,最后还要考虑多余的那部分2对结果的影响。
step4:output your answer!

正如上面文章里所说的“To compute the number of 3,7,9 among (f(1) mod 10), (f(2) mod 10), ..., (f(N) mod 10) is not so easy”,这里面步骤2是个难点。如何求出剩下的这串数字相乘后最后一位是几呢?这可以转化成求出这些数里面末尾是3,7,9的数字出现的次数(为啥?因为这些数的n次方是有规律的,周期为4,不信你可以推一下)
好,现在问题就是如何求出这串数字中末尾3,7,9各自出现的次数了;

一个数列实际上可以分成偶数列和奇数列,以1*2*3*4*5*6*7*8*9*10为例

分成1 3 5 7 9,   2 4 6 8 10

这样我们尝试分别进行统计,可以发现,实际上2,4,6,8,10中的个数也就是1 2 3 4 5中的个数,也就是说我们又把这个问题划分成了一个原来问题的子问题。

f(n) = f(n/2) + g(n),g(n)表示奇数列中的数目,所以我们需要解决g(n)

再次观察g(n)

实际上又分成了两部分1 3 7 9 11 13 17 19 21。。。以及5的奇倍数5,15,25。。。说明又出现了子问题,如果要统计这个数列中末尾为x(1,3,7,9)的个数可以这样写:g(n,x) = n/10+(n%10 >= x)+g(n/5,x)

这样利用了两个递归方程,我们就可以在lgn的时间内计算出末尾为1,3,7,9的数的个数了

 

好了,现在我们得到了这串数字中末尾是3,7,9的数字的个数,我们利用循环节的性质可以快速地算出这串数字相乘后mod 10的结果,在考虑下当时多除的2(其实也可以用循环节来处理),便可求出答案!


解决了上面两个子问题,我想求P(n,m)最后一个非0位就变得十分容易了。
P(n,m)实际上等于 n! / (n-m)!
我们可以求出n! 和(n-m)!中质因数2,5,3,7,9分别出现的次数,然后再各自相减。
然后再用循环节处理,即可!
BTW,这里还要注意一个trick,就是2的出现次数如果小于5,(这对于排列数来说是可能的)我们可以直接输出5,如果2的数目等于5,那么2的循环节不需要考虑。至于3,7,9的循环节,由于这些数的4次方末位刚好是1,所以就不需要特殊考虑了。