Euler 160: Tìm 5 số không nhỏ của giai thừa

Question

Cho số tìm 5 chữ số trước dấu 0. = 362880 để f (9) = 36288 10! = 3628800 để f (10) = 36288 20! = 2432902008176640000 nên f (20) = 17.664 Find f (1.000.000.000.000)

Đối với điều này tôi đã tính toán các f(10^6) và sau đó f(10^12) = (f(10^6))^(10^6) để tính f(n) ... Tôi đang tính toán thừa bằng cách loại bỏ bất kỳ 5 và tương ứng 2 để tất cả các sốkhông được xóa.
Nhưng tôi nhận được câu trả lời sai.
Có vấn đề gì trong cách tiếp cận hoặc một số sai lầm ngớ ngẩn không?

Mã để tham khảo

long long po(long long n, long long m, long long mod) { 
    if (m == 0) return 1; 
    if (m == 1) return n % mod; 
    long long r = po(n, m/2, mod) % mod; 
    if (m % 2 == 0) return (r * r) % mod; 
    return (((r * r) % mod) * n) % mod; 
} 

void foo() { 
    unsigned long long i, res = 1, m = 1000000 , c = 0, j, res1 = 1, mod; 
    mod = ceil(pow(10, 9)); 
    cout << mod << endl; 
    long long a = 0, a2 = 0, a5 = 0; 
    for (i = 1 ; i <= m; i++) { 
     j = i; 
     while (j % 10 == 0) 
      j /= 10; 
     while (j % 2 == 0) { 
      j /= 2; 
      a2++; 
     } 
     while (j % 5 == 0) { 
      j /= 5; 
      a5++; 
     } 
     res = (res * j) % mod; 
    } 

    a = a2 - a5; 

    for (i = 1; i <= a; i++) 
     res = (res * 2) % mod; 
    for (i = 1; i <= 1000000; i++) { 
     res1 = (res1 * res) % mod; 
    } 
    cout << res1 << endl; 
} 

Answer 1

bình đẳng của bạn f(10^12) = (f(10^6))^(10^6) là sai. f() dựa trên giai thừa, chứ không phải quyền hạn.

Answer 2

giả định của bạn là sai lầm:

• f (10^12) là không giống như f (10^6)^(10^6).
• để nhận được thứ tự không 0 chữ số của giai thừa, nó không đủ để loại bỏ tất cả bội số của 10, 2 và 5 từ các phép nhân. Việc xóa bội số của 10 là một ý tưởng hay, đối với 5 và 2, bạn chỉ nên loại bỏ hệ số 2 hoặc 5 nếu các bội số khác là bội số của 5 và 2 tương ứng.

Bạn nên đơn giản hóa mã và tính toán modulo một số sức mạnh của 10, nhưng 10^9 dường như quá cao như 10^9 * 10^12 sẽ tràn 64-bit kiểu unsigned long long.