Project Euler - Sự cố 160

Question

Đối với bất kỳ N nào, hãy f (N) là năm cuối cùng chữ số trước dấu 0 ở số N !. Ví dụ,

9! = 362880 so f(9)=36288 
10! = 3628800 so f(10)=36288 
20! = 2432902008176640000 so f(20)=17664 

Tìm f (1.000.000.000.000)

Tôi đã giải quyết thành công vấn đề này cho các ví dụ được đưa ra, chức năng của mình một cách chính xác có thể tìm thấy f (9), f (10), vv Tuy nhiên nó đấu tranh với số lượng lớn hơn, đặc biệt là số vấn đề yêu cầu - f (10^12).

Tối ưu hóa hiện tại của tôi như sau: Tôi xóa số không theo sau khỏi hệ số và tổng, và rút ngắn tổng thành 5 chữ số sau mỗi phép nhân. Mã trong python như sau:

def SFTR (n): 
sum, a = 1, 2 
while a < n+1: 
    mul = int(re.sub("0+$","",str(a))) 
    sum *= mul 
    sum = int(re.sub("0+$","",str(sum))[-5:]) 
    a += 1 
return sum 

Bất cứ ai có thể cho tôi biết lý do tại sao chức năng này được mở rộng quá nhiều và lý do mất quá nhiều thời gian. Ngoài ra, nếu có ai có thể gợi ý cho tôi theo hướng đúng để tối ưu hóa thuật toán của tôi. (tên của chủ đề chung sẽ đủ) Cảm ơn bạn.

Cập nhật:

Tôi đã thực hiện một số thay đổi để tối ưu hóa và nó là nhanh hơn đáng kể, nhưng nó vẫn không đủ nhanh cho f (10^12). Bất cứ ai có thể cho tôi biết whats làm cho mã của tôi chậm hoặc làm thế nào để làm cho nó nhanh hơn?

def SFTR (n): 
    sum, a = 1, 2 
    while a < n+1: 
     mul = a 

     while(mul % 10 == 0): mul = mul/10 
     mul = mul % 100000 

     sum *= mul 

     while(sum % 10 == 0): sum = sum/10 
     sum = sum % 100000 

     a += 1 
    return sum 

Answer 1

mul có thể rất lớn. Điều đó có cần thiết không? Nếu tôi yêu cầu bạn tính toán 5 chữ số khác 0 của 1278348572934847283948561278387487189900038 * 38758 bằng tay, chính xác bạn cần biết bao nhiêu chữ số đầu tiên?

Answer 2

Chuỗi xây dựng thường tốn kém. Tôi muốn sử dụng toán tử modulo khi cắt ngắn năm chữ số cuối cùng.

python -m timeit 'x = str(111111111111111111111111111111111)[-5:]' 
1000000 loops, best of 3: 1.09 usec per loop 
python -m timeit 'x = 111111111111111111111111111111111 % 100000' 
1000000 loops, best of 3: 0.277 usec per loop 

Điều tương tự cũng áp dụng cho việc tước các số không theo sau. Nên có một cách hiệu quả hơn để làm điều này, và bạn có thể không phải làm điều đó trong từng bước.

Tuy nhiên, tôi đã không kiểm tra tính chính xác của thuật toán, đó chỉ là gợi ý tối ưu hóa.

Answer 3

Trong thực tế, bạn thậm chí có thể lưu ý rằng chỉ có một tập hợp có giới hạn các số có thể có khác 0. Nếu tôi nhớ lại chính xác, chỉ có một vài nghìn kết hợp có thể có chữ số không khác, khi bạn chỉ nhìn vào 5 chữ số cuối cùng. Ví dụ, có thể cho con số cuối cùng khác không bao giờ là lẻ? (Bỏ qua các trường hợp đặc biệt là 0! Và 1! Ở đây.)