Factorials

The factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Likewise, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.

PROGRAM NAME: fact4

INPUT FORMAT

A single positive integer N no larger than 4,220.

SAMPLE INPUT (file fact4.in)

7

OUTPUT FORMAT

A single line containing but a single digit: the right most non-zero digit of N! .

SAMPLE OUTPUT (file fact4.out)

4 ———————————————————————————— 以为一个个把个位乘起来%10就好了，然并不，有些时候 例如75*4和74*14的最右非零位是不一样的，其实我们只需要手动去除2和5这两个质因子剩下的乘起来%10就可以了 纪念我的智障……

1 /* 2 ID: ivorysi 3 PROG: fact4 4 LANG: C++ 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           12 #include 
           
            13 #define siji(i,x,y) for(int i=(x);i<=(y);++i)14 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)15 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)16 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)17 #define inf 0x7fffffff18 #define MAXN 40000519 #define ivorysi20 #define mo 9779797721 #define ha 97471122 #define ba 4723 #define fi first24 #define se second25 //#define pis pair
            
             26 using namespace std;27 typedef long long ll;28 int two,five;29 int n;30 int ans=1;31 void divide(int &u) {32 while(u%5==0) {++five;u/=5;}33 while(u%2==0) {++two;u/=2;}34 }35 void solve() {36 scanf("%d",&n);37 siji(i,1,n) {38 int tmp=i;39 divide(tmp);40 ans=(ans*tmp+10)%10;41 }42 two-=five;43 siji(i,1,two) ans=ans*2%10;44 printf("%d\n",ans);45 }46 int main(int argc, char const *argv[])47 {48 #ifdef ivorysi49 freopen("fact4.in","r",stdin);50 freopen("fact4.out","w",stdout);51 #else52 //freopen("f1.in","r",stdin);53 #endif54 solve();55 }