Cần trợ giúp câu hỏi thực hành Codechef - tìm các số 0 trong một giai thừa

Question

Tôi đã làm việc này trong 24 giờ, cố gắng tối ưu hóa nó. Câu hỏi đặt ra là làm thế nào để tìm số lượng dấu 0 trong giai thừa của một số trong khoảng 10000000 và 10 triệu trường hợp thử nghiệm trong khoảng 8 giây.

Mã này là như sau:

#include<iostream> 

using namespace std; 

int count5(int a){ 
    int b=0; 
    for(int i=a;i>0;i=i/5){ 
     if(i%15625==0){ 
      b=b+6; 
      i=i/15625; 
     } 
     if(i%3125==0){ 
      b=b+5; 
      i=i/3125; 
     } 
     if(i%625==0){ 
      b=b+4; 
      i=i/625; 
     } 
     if(i%125==0){ 
      b=b+3; 
      i=i/125; 
     } 
     if(i%25==0){ 
      b=b+2; 
      i=i/25; 
     } 
     if(i%5==0){ 
      b++; 
     } 
     else 
      break; 

    } 
    return b; 
} 
int main(){ 
    int l; 
    int n=0; 
    cin>>l; //no of test cases taken as input 
    int *T = new int[l]; 

    for(int i=0;i<l;i++) 
     cin>>T[i]; //nos taken as input for the same no of test cases 


    for(int i=0;i<l;i++){ 
     n=0; 
     for(int j=5;j<=T[i];j=j+5){ 
      n+=count5(j); //no of trailing zeroes calculted 
     } 
     cout<<n<<endl; //no for each trialing zero printed 
    } 

    delete []T; 


} 

Xin hãy giúp tôi bằng cách gợi ý một cách tiếp cận mới, hoặc gợi ý một số thay đổi với trang này.

Answer 1

Sử dụng định lý sau:

Nếu p là số nguyên tố, thì quyền lực cao nhất của p mà chia n! (n giai thừa) là [n/p] + [n/p^2] + [n/p^3] + ... + [n/p^k], trong đó k là lũy thừa lớn nhất của p < = n và [x] là phần không thể tách rời của x.

tham khảo: http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html

Answer 2

Giải pháp tối ưu chạy trong O(log N) thời gian, nơi N là số bạn muốn tìm zero cho. Sử dụng công thức này:

Zeroes(N!) = N/5 + N/25 + N/125 + ... + N/5^k, cho đến khi phân chia thành 0. Bạn có thể đọc thêm trên wikipedia.

Vì vậy, ví dụ, trong C này sẽ là:

int Zeroes(int N) 
{ 
    int ret = 0; 
    while (N) 
    { 
     ret += N/5; 
     N /= 5; 
    } 
    return ret; 
} 

này sẽ chạy trong 8 giây trên một máy tính đủ nhanh. Bạn có thể tăng tốc nó bằng cách sử dụng bảng tra cứu, mặc dù tôi không chắc chắn bạn có bao nhiêu bộ nhớ.

Đây là một đề xuất khác: không lưu trữ các số, bạn không cần chúng! Tính số zeroes cho mỗi số khi bạn đọc nó.

Nếu điều này là cho một thẩm phán trực tuyến, trong kinh nghiệm của tôi trực tuyến thẩm phán phóng đại giới hạn thời gian về các vấn đề, vì vậy bạn sẽ phải nghỉ mát hacks xấu xí ngay cả khi bạn có các thuật toán đúng. Một lỗi xấu xí như vậy là không sử dụng các chức năng như cin và scanf, nhưng thay vào đó hãy sử dụng fread để đọc một loạt dữ liệu cùng một lúc trong mảng char, sau đó phân tích dữ liệu đó (KHÔNG sử dụng sscanf hoặc stringstreams) và nhận các số ra khỏi nó. Xấu xí, nhưng nhanh hơn rất nhiều.

Answer 3

Bạn đã biết rõ thuật toán chính xác. Các nút cổ chai trong mã của bạn là việc sử dụng cin/cout. Khi giao dịch với đầu vào rất lớn, cin cực kỳ chậm so với scanf.

scanf cũng chậm hơn so với phương thức đọc đầu vào trực tiếp như fread, nhưng việc sử dụng scanf là đủ cho hầu hết các vấn đề về thẩm phán trực tuyến.

này được trình bày chi tiết trong Codechef FAQ, mà có lẽ là đáng đọc đầu tiên;)

Answer 4

Câu hỏi này là từ codechef.

http://www.codechef.com/problems/FCTRL

Làm thế nào về giải pháp này:

#include <stdio.h> 

int a[] = {5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625}; 

int main() 
{ 
    int i, j, l, n, ret = 0, z; 
    scanf("%d", &z); 
    for(i = 0; i < z; i++) 
    { 
     ret = 0; 
     scanf("%d", &n); 
     for(j = 0; j < 12; j++) 
     { 
      l = n/a[j]; 
      if(l <= 0) 
       break; 
      ret += l; 
     } 
     printf("%d\n", ret); 
    } 
    return 0; 
} 

Bất kỳ tối ưu hóa ???

Answer 5

Knows này là hơn 2 tuổi nhưng đây là mã của tôi để tham khảo trong tương lai:

#include <cmath> 
#include <cstdio> 

inline int read() 
{ 
    char temp; 
    int x=0; 
    temp=getchar_unlocked(); 
    while(temp<48)temp=getchar_unlocked(); 
    x+=(temp-'0'); 
    temp=getchar_unlocked(); 
    while(temp>=48) 
    { 
     x=x*10; 
     x+=(temp-'0'); 
     temp=getchar_unlocked(); 
    } 
    return x; 
} 
int main() 
{ 
    int T,x,z; 
    int pows[]={5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625}; 
    T=read(); 
    for(int i=0;i<T;i++) 
    { 
     x=read(); 
     z=0; 
     for(int j=0;j<12 && pows[j]<=x;j++) 
      z+=x/pows[j]; 
     printf("%d\n",z); 
    } 
    return 0; 
} 

Nó chạy trong 0.13s

Answer 6

Đây là giải pháp chấp nhận tôi. Điểm số của nó là 1,51s, 2,6M. Không phải là tốt nhất, nhưng có lẽ nó có thể giúp bạn.

#include <iostream> 
using namespace std; 

void calculateTrailingZerosOfFactoriel(int testNumber) 
{ 

    int numberOfZeros = 0; 
    while (true) 
    { 

     testNumber = testNumber/5; 
     if (testNumber > 0) 
      numberOfZeros += testNumber; 
     else 
      break; 
    } 
    cout << numberOfZeros << endl; 
} 

int main() 
{ 

    //cout << "Enter number of tests: " << endl; 
    int t; 
    cin >> t; 

    for (int i = 0; i < t; i++) 
    { 
     int testNumber; 
     cin >> testNumber; 
     calculateTrailingZerosOfFactoriel(testNumber); 
    } 
    return 0; 
} 

Answer 7

#include <cstdio> 

int main(void) { 
    long long int t, n, s, i, j; 
    scanf("%lld", &t); 
    while (t--) { 
     i=1; s=0; j=5; 
     scanf("%lld", &n); 
     while (i != 0) { 
      i = n/j; 
      s = s + i * (2*j + (i-1) * j)/2; 
      j = j * 5; 
     } 
     printf("%lld\n", s); 
    } 
    return 0; 
}