算法与acm

poj1150 the last nozero digit

2008年11月16日 阅读(67)

转载请注明作者: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));
    }
}

You Might Also Like