阶乘浅析poj1150 3406 zoj1222 2358
阶乘问题分为几类：
1.求阶乘末尾0的个数，，直接除以5，累加即可。
2.求阶乘的结果一共有多少位，stirling公式：n！≈sqrt(2*PI*n) * (n/e)^n，直接取以10为底的对数，整数部分即为位数。 3.求阶乘的最后非零位，这类问题比较复杂，专题中我们着重讨论这个问题
首先看POJ1150
题目大意：求n的m排列的最后非零位。
题目分析：n的m排列即P(n,m)=n!/(n-m)!，所以这题是求两个阶乘商的最后非零位。我们处理阶乘时一般是逐个处理。首先看普遍性的对于一个数n的阶乘，我们如何处理它的末尾非零位。
10的因子是2和5，这两个数不属于模10的缩系，所以我们在处理数时要剔除掉这两个因子，剔除所有数中含5和2这两个因子。
首先我们用f(n,x)表示小于等于n的数中，末尾位x的数的个数。n我们可以分解为1,3,5,7,9... 2,4,6,8,10...
因为我们将偶数中的2因子剔除了，所以2,4,6,8,10...实际上又变成了1,3,5,7,9...
所以我们可以得到递推式f(n,x)=f(n/2,x)+g(n,x)，g(n,x)表示的是小于等于n的奇数中尾数为x的数的个数。
那么g(n,x)怎么求呢，首先n/10必定是其中一部分，其次要看n>=x是否成立，成立就加1，不成立就不加。最后一点要注意，我们在奇数中还有汗5因子的数，所以要剔除掉5这个因子，比如5 15 25 35 45... 剔除了5之后又变成了1 3 5 7 9...，所以g(n,x)=n/10+(n%10>=x)+g(n/5,x)。
有了这两个递推式再加上求5因子和2因子个数的递归除法，我们很快就能得到2因子个数，5因子个数，末尾位3 7 9因子的个数。下面我们要列个循环表mod2[4]={6,2,4,8},mod3[4]={1,3,9,7},mod7[4]={1,7,9,3},mod9[4]={1,9,1,9}，表示的是各个因子自己相乘时尾数的循环节，这里要特别注意一点，由于2非模10的缩系，所以2^0=1，这一点要格外注意，所以只有它循环节不是从0开始，0要单独处理。因为n-m的阶乘必定是n的阶乘的子集，所以我们可以直接用因子数相减即可。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5);
cnt[3]=get(n,3)-get(n-m,3);
cnt[7]=get(n,7)-get(n-m,7);
cnt[9]=get(n,9)-get(n-m,9);
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]<cnt[5]){res*=5;}
res=res*mod3[cnt[3]%4]*mod7[cnt[7]%4]*mod9[cnt[9]%4];
printf("%d\n",res%10);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5);
cnt[3]=get(n,3)-get(n-m,3);
cnt[7]=get(n,7)-get(n-m,7);
cnt[9]=get(n,9)-get(n-m,9);
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]<cnt[5]){res*=5;}
res=res*mod3[cnt[3]%4]*mod7[cnt[7]%4]*mod9[cnt[9]%4];
printf("%d\n",res%10);
}
return 0;
}
再来看POJ3406
求n!/(m!*(n-m)!)的最后非零位
与上题一样，但是由于m的阶乘和n-m的阶乘的乘积并不是n的阶乘的子集，但是我们可以通过观察发现，只有n的阶乘中3的个数会少于m的阶乘和n-m的阶乘3的数目之和，但是我们不要担心，这个时候我们可以通过将n的阶乘中的9的个数分解得到。还有一种方法是再多加一个循环模（我表示不理解）
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[8];
int mod2[4]={6,2,4,8};
int mod3[4]={1,3,9,7};
int mod7[4]={1,7,9,3};
int mod9[4]={1,9,1,9};
int getpow(int n,int k)
{
int sum=0;
while(n)
{
sum+=n/k;
n/=k;
}
return sum;
}
int g(int n,int k)
{
if(n==0)return 0;
return n/10+(n%10>=k)+g(n/5,k);
}
int get(int n,int k)
{
if(n==0)return 0;
return get(n/2,k)+g(n,k);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int res=1;
memset(cnt,0,sizeof(cnt));
cnt[2]=getpow(n,2)-getpow(n-m,2)-getpow(m,2);
cnt[5]=getpow(n,5)-getpow(n-m,5)-getpow(m,5);
cnt[3]=get(n,3)-get(n-m,3)-get(m,3);
cnt[7]=get(n,7)-get(n-m,7)-get(m,7);
cnt[9]=get(n,9)-get(n-m,9)-get(m,9);
cnt[3]+=cnt[9]*2;cnt[9]=0;
if(cnt[2]>cnt[5]){res*=mod2[(cnt[2]-cnt[5])%4];}
else if(cnt[2]<cnt[5]){res*=5;}
res=res*mod3[cnt[3]%4]*mod7[cnt[7]%4]*mod9[cnt[9]%4];
补充：软件开发 , C++ ,
