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

Go down

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

Bài gửi  ductam on Tue Aug 31, 2010 11:47 pm

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);
 }
}
cung hi
avatar
ductam
Thành viên cấp 2
Thành viên cấp 2

Tổng số bài gửi : 11
Ngày tham gia : 18/07/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết