Description

描述

阶乘是一个很恐怖的东西哦~

N的阶乘=1*2*3*4*…*N。当N很大时，阶乘的长度自然很大。

当然，我们需要的程序不是要你写出N的阶乘的具体数字，而是要你给出N的阶乘的末尾0的个数和末尾去除0的数字。简单吧~~~~（传说中有个叫YYD的人不屑于做这个题目！！！）

Input

一行 N

Output

两行，第一行为0的个数，第二行为末尾去除0的数字。

Sample Input

 

10

 

Sample Output

 

28

 

Hint

10!=3628800，末尾有2个0，去处0后末尾的数字为8。

数据范围

0<=N<=10^16

对于30%的数据 N<=5000000

对于100%的数据 N<=10^16 

 

题解：http://www.cnblogs.com/jiangjun/articles/2491276.html

最后用中国剩余定理合并一下就行了

code：

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 typedef long long int64; 8 char ch; 9 const int64 fac[5]={
   1,1,2,6,24};10 const int64 power[4]={
   1,3,9,27};11 int64 n,c,ans;12 bool ok;13 void read(int64 &x){14     for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;15     for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());16     if (ok) x=-x;17 }18 int main(){19     read(n);20     if (n==0||n==1){puts("0"),puts("1");return 0;}21     ans=1;22     while (n) c+=n/5,ans*=fac[n%5],ans%=5,n/=5;23     if (c&1) ans*=-1,ans+=5,ans%=5;24     printf("%I64d\n",c);25     printf("%I64d\n",6*ans*power[c%4]%10);26     return 0;27 }