Tìm chữ số tận cùng khác 0 của N!

[ductam]

Link đề bài: http://vn.spoj.pl/problems/TCDFZ/
Đề bài:
937. Chữ số tận cùng khác 0
Mã bài: TCDFZ

Cho số tự nhiên n (n <= 10^9). Hãy tìm chữ số tận cùng khác 0 của n!
Input

- Dòng duy nhất ghi số N.
Output

- Gồm 1 dòng duy nhất ghi kết quả tìm được.
Example

Input:
5

Output:
2

Thuật toán:
Bài này có một thuật toán ngây thơ như sau mà chắc chắn coder nào cũng nghĩ đến.
kq=1
for i=1-->N
{
kq=kq*i
while(kq%10==0) kq=kq/10
}
Xuất kq là đáp án bai toán. Tuy nhiên nếu làm theo thuật toán này thi khi n=10^9-->TLE.
Vì vậy mà để xử lý bài này thì code of mine như sau, nếu member nào quan tâm thì mình có thể giải thích chi tiết. Bài này kể từ khi biết đề cho đến khi mình giải được đã xấp xỉ 2 năm cơ đấy.
Code:

Code:


#include<stdio.h>
//  #include<conio.h>

long int N;
int kq=1;
int ex[11];
int Pow(int x,int exp);

int main()
{
    int chusocuoi;
    long int tam;
    int i;
    long int num,numdiv5,numdis;
    int mod;
    scanf("%ld",&N);
    while(N!=0)
    {
    numdis=N/10;
    for(i=1;i<10;i++) ex[i]=numdis+1;
    mod=N%10;
    for(i=mod+1;i<10;i++) ex[i]--;
    //Test
  /*  for(i=1;i<10;i++) if(i!=5)
                      {
                        printf("i=%d    ex[%d]=%d\n",i,i,ex[i]);       
                      }
    getch(); */
    for(i=1;i<10;i++) if(i!=5) kq=(kq*Pow(i,ex[i]))%10;
    numdiv5=N/5;
    int t=numdiv5%4;
    for(i=0;i<t;i++)
    if(kq==8) kq=4;
    else if(kq==4) kq=2;
          else if(kq==2) kq=6;
              else if(kq==6) kq=8;
    N=N/5;         
    }
    printf("%d",kq);
  //  getch();
    return 0;
}
int Pow(int x,int exp)
{
 if(exp==0) return 1;
 else
 {
 if(exp%2==0)
 {
              int tam;
              tam=Pow(x,exp/2);
              return (tam*tam)%10;
 }
 else return((x*Pow(x,exp-1))%10);
 }
}