【描述】
N的阶乘写作N!表示小于等于N的所有正整数的乘积。阶乘会很快的变大，如13!就必须用32位整数类型来存储，70！即使用浮点数也存不下了。你的任务是找到阶乘最后面的非零位。举个例子,5!=1*2*3*4*5=120所以5!的最后面的非零位是2，7！=1*2*3*4*5*6*7=5040，所以最后面的非零位是4。
【格式】
PROGRAM NAME: rect4
INPUT FORMAT:(file rect4.in)
共一行，一个整数不大于4，220的整数N。
OUTPUT FORMAT:(file rect4.out)
共一行，输出N!最后面的非零位。
【分析】
先打素数表，然后分解质因数，再去掉可以产生末尾0的2和5(不是所有二和五，而是他们的最小值)，最后在把剩下的乘起来MOD10。
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 const int maxn=4220; 7 using namespace std; 8 int cnt[maxn],vis[maxn]; 9 int prime[maxn]; 10 void built_prime();//打表 11 void check(int n); 12 int pow_mod(int num,int t); 13 int main() 14 { 15 int n,i,temp,ans=1; 16 //文件操作 17 freopen("fact4.in","r",stdin); 18 freopen("fact4.out","w",stdout); 19 built_prime(); 20 //printf("1"); 21 scanf("%d",&n); 22 for (i=1;i<=n;i++) check(i);//分解质因数 23 temp=min(cnt[2],cnt[5]); 24 cnt[2]-=temp;cnt[5]-=temp; 25 for (i=1;i<=prime[0];i++) 26 { 27 if (cnt[prime[i]]!=0) 28 ans=(ans*pow_mod(prime[i],cnt[prime[i]]))%10;//快速幂取模 29 } 30 printf("%d",ans%10); 31 return 0; 32 } 33 int pow_mod(int num,int t) 34 { 35 if (t==1) return num%10; 36 if (t==2) return (num*num)%10; 37 int temp=pow_mod(num,t/2); 38 if (t%2==0) return (temp*temp)%10; 39 else return (temp*temp*num)%10; 40 } 41 void built_prime() 42 { 43 int i,j; 44 memset(cnt,0,sizeof(cnt)); 45 prime[0]=0; 46 for (i=2;i<=maxn;i++) 47 { 48 if (vis[i]==0) 49 { 50 prime[++prime[0]]=i; 51 for (j=i;j<=maxn;j+=i) vis[j]=1; 52 } 53 } 54 } 55 void check(int n) 56 { 57 int i; 58 while (n!=1) 59 { 60 for (i=1;i<=prime[0];i++) 61 if (n%prime[i]==0) {cnt[prime[i]]++;n=n/prime[i];break;} 62 } 63 }