转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720081016113033592/
http://acm.pku.edu.cn/JudgeOnline/problem?id=1150
最最原始的问题，是那个计算n!的结果中的0的个数的问题，对于这个问题的解答是，我们只需要观察1*2*3...n的因子中，因子5的个数就可以了。因为末尾0的个数，实际上反映了结果中因子10的个数，而10=2*5，由于在1*2*3...n中，2的个数始终是大于5的，所以10的个数实际上是由因子5的个数决定的，所以需要计算出5的个数就好了。
那怎么计算因子5的个数呢？
是利用了递归，f(n) = n/5 + f(n/5)
可以这样理解，对于1 2 3 4 5 6 7 8 9 10 .....
首先可以看到含有因子5的数必然是5的整数倍，5，10，15，20，25
我们首先从这些数抽取出一个5，可以抽取出的5的个数就是n/5,而这些数抽取出一个5后，变成了1,2,3,4....n/5
所以变成了一个子问题，故递归可解。
进一步的计算 n!的最后一个非0位
这个问题要比上一个问题难，但是依旧要利用递归，以及2，5
对于这样的一系列数的乘法，它的最后一位是怎么形成的呢，首先2*5组成了那些0位，所以相同数目的2，5对最后一个非0位没有影响，所以我们可以把2，5分解掉，但是有时候2的个数是大于5的，所以我们还要记住剩下的2的个数，因为它是对最后结果有影响的。然后我们需要观察其他数的最后一位，因为这些最后一位对最终n!的结果形成了影响。
以1*2*3*4*5*6*7*8*9*10为例
第一步，我们需要把这些数里，因子2和5分解出去，变成
1*1*3*1*1*3*7*1*9*1
(容易看出，当对于任意的一个数x，当因子2，和5分解出去后，它的最后一位必然是1，3，7，9中的某一个)
所以我们只要能够统计出这个结果中，1，3，7，9的个数就能最终求出n!的最后一位了
所以关键在于统计末尾为1，3，7，9的个数，这个统计的方法就需要我们继续观察了。
第二步，统计除去因子2，5后末尾为1，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的数的个数了
最终，我们还要加上剩余的2来共同决定最后的一个非0位，而对于1，2，3，7，9他们的乘法的最后一位也是有循环节的，以2为例，连续的2相承，最后一位是这样的一个循环2，4，8，6，2，4，8，6........
这样我们就得到了计算n!最后一个非0位的方法。
计算n!/（n-m）!的最后一个非零位。
因为(n-m)!是n！的一个子集，所以我们只有分别计算出它们中2，3，7，9的个数，然后用n!的减去（n-m）!的，就是最终n*n-1*。。。n-m+1的。也就是poj1150的解法。
计算n!/(m!*(n-m)!)也就是C(n,m)的最后一个非零位----poj3406
因为(m!*(n-m)!)不是n!的一个子集，所以这个不能利用1150的方法,而且观察它的input,实际上只有一个case，而且n ，m< 1000000，所以nlogn的方法是可以过的。
但是我们可以采用最简单的思路来解它，也就是直接遍历，对于每个数，计算2，5因子数，以及把它的因子2，5去除剩余的最后一位，最后把这些最后一位相乘，再求最后一位再考虑多余的2.5，然后求出最后一位。思路一样，但是求解2，5，3，7，9的方法采用了遍历的方法，而不是递归了。。。
附1150代码：#include <stdio.h>
#include <string.h>
//using namestd std;
#define DEBUG 1
#undef DEBUG
int get2(int n){
if(n == 0) return 0;
return n/2+get2(n/2);
}
int get5(int n){
if(n == 0) return 0;
return n/5+get5(n/5);
}
int odd_getX(int n,int x){
if(n == 0) return 0;
return n/10+(n%10 >= x)+ odd_getX(n/5,x);
}
int getX(int n,int x){
if(n == 0) return 0;
return getX(n/2,x)+odd_getX(n,x);
}
int solve(int n,int m){
int two,five,one,three,seven,nine;
int table[4][4] ={
6,2,4,8,//last digit of 2^4 2 2^2 2^3
1,3,9,7,//...3
1,7,9,3,//...7
1,9,1,9,//...9
};
m = n-m;
two = get2(n)-get2(m);
five = get5(n)-get5(m);
one = getX(n,1) - getX(m,1);
three = getX(n,3) - getX(m,3);
seven = getX(n,7) - getX(m,7);
nine = getX(n,9) - getX(m,9);
#ifdef DEBUG
printf("2:%d 5:%d\n",two,five);
printf("1:%d 3:%d 7:%d 9:%d\n",one,three,seven,nine);
#endif
int last_digit = 1;
if(two < five) return 5;
else{
if(two > five) last_digit *= table[0][(two-five)%4];
last_digit *= table[1][three%4];
last_digit *= table[2][seven%4];
last_digit *= table[3][nine%4];
return last_digit % 10;
}
}
int main()
{
int n,m;
//assume num of draw is x,non-draw is y
//we can get x+y = N and 2*x+3*y = sum(score);so we can get x =...
while(scanf("%d%d",&n,&m) == 2)
{
printf("%d\n",solve(n,m));
}
}
评论