N!的非零位求法以及末尾零的个数的求法

//首先求末尾零的个数的求法，就是求5的因子的个数，因为2×5得到一个0.
//这个函数函数求1-N因子个数的求法
int cali(int n,int i){
 int ret = 0;
 while(n){
  n /= i;
  ret += n;
 }
 return ret;
}

当i=5时，就可以用来求：N！的末尾的零的个数。

问题是求关于N!的最后一位非0位, 如3!=6,最后一位非0位为6, 5!=120, 最后一位非0位为2.怎么样快速的求出最后一位非0位呢?

最朴素的想法就是先求出N!的结果,再求出结果的最后一位非0位.当N比较小时,是可以承受的,但是当N达到一定规模的时候,时间,空间都不会太理想.这里需要一些技巧.既然是求最后一位非0位,我们就可以先除非所有对结果没有影响的数,如10的倍数.于是先把N!因子分解得到形如2^a5^bc.这个时候我们去掉一个b个5因子和b个2因子,最后一位非0位是不变的.(N!中2的因子一定不会比5的因子少).于是我们的要求的结果就变为(2^(a-b)c)%10.由(ab)%10=((a%10)(b%10))%10我们可以得((2^(a-b)%10)(c%10))%10,由于c不会产生未位为0,故只保留c的最未位即可.于是可将c转化为1,3,7,9因子的相乘得到的结果的最未位(因为1,3,7,9因子相乘不会产生最未非0位,故去掉高位不会对结果产生影响,同时1*n=n可以去掉1的因子).

2,3,7,9因子规律如下:

 2^1=2, 2^2=4, 2^3=8, 2^4=16->(6), 2^5=32->(2)

3^0=1, 3^1=3, 3^2=9, 3^3=27->(7), 3^4=81->(1)

7^0=1, 7^1=7, 7^2=49->(9), 7^3=343->(3), 7^4=2401->(1)

9^0=1, 9^1=9, 9^2=81->(1), 9^3=729->(9), 9^4=6561->(1)

它们都是以4为循环周期的.于是我们只要求出2, 5, 3, 7, 9因子的个数即可.

首先我们求2,5因子在N!中的个数.2的因子的每个偶数到少有1个,同时将数列中每个数/2,其中的偶数还有一个2因子.直至n=1或n=0结束.5因子求法相同.代码直接调用cali(2)和cali(5)就行

3,7,9因子的个数有多少呢?对于1,2,3,4……n-1,n来说,未尾以3,7,9结束的数的个数为n/10+(n%10³f?1:0),(f=3,7, 9).同时我们对于对于奇数数列/5可以得到一个新的数列也有3,7,9因子,对于偶数数列/2也可以得到新的数列也有3,7,9的因子,将所有的3,7,9因子相加即可得到总的3,7,9因子的个数.得到3,7,9因子的个数后,我们可以将其全部转化为因子3的个数.因为9=33(3^2), 7=(333(3^3))%10,设f3, f7, f9为3, 7, 9因子的个数,全部转化为因子3的个数为f3+2f9+3*f7.

于是我们可以用递归同时求2,3,5,7,9因子的个数,代码如下:

void solve(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;
 solve(n/2);
}

然后N！末尾零便是：

ans[n] = (1*pmod(2,co2-co5)*pmod(3,co3)*pmod(7,co7)*pmod(9,co9))%10;

pmod函数：

inline int pmod(int n,int k){
    int ret = 1;
    while (k){
        if (k&1) ret = ret * n % 10;
        n = n * n %10;
        k >>= 1;
    }
    return ret;
}

例题：POJ 1604

其实通过N!的最未非0位的方法我们可以求排列组合数^NP_M,C(N,M)的最未非0位,用上面的各因子个数减去下面的各因子个数就是结果的各因子个数.只是此时需要注意的是5的因子可能会比2的因子多.当5的因子比2的因子多时,未位一定为5.其余情况与上面相同.

例题：POJ3406和POJ1150