阶乘之和

Description

描述
阶乘是一个很恐怖的东西哦~
N的阶乘=1*2*3*4*…*N。当N很大时，阶乘的长度自然很大。
当然，我们需要的程序不是要你写出N的阶乘的具体数字，而是要你给出N的阶乘的末尾0的个数和末尾去除0的数字。简单吧~~~~（传说中有个叫YYD的人不屑于做这个题目！！！）

Input

一行 N

Output

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

Sample Input

Sample Output

2
8

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<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 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
",c);
25     printf("%I64d
",6*ans*power[c%4]%10);
26     return 0;
27 }