Tính giai thừa dùng số nguyên lớn

Mọi người có ai biết cách tính giai thừa của một số nguyên lớn (1 tỷ) không? Mình đang gặp bài này và đang bí, tìm trên google không ra thuật toán. Mong mọi người giúp

Cảm ơn bạn nhưng thuật toán này mình đã đọc qua và có vẻ như không tính được đến 1 tỷ giai thừa. Dù sao cũng cảm ơn

(10^9)!=10^10^9.932763139878869 wtf


https://gmplib.org/manual/Factorial-Algorithm.html

3 Likes

Swing factorial :slight_smile: (không phải Java Swing à)

Đặt swing(n) = n! / ((n DIV 2)!)^2, vậy (2n)! = n!^2 * swing(2n) (cũng như với (2n+1)!) Ta thấy cũng khá giống C(n, n DIV 2). Thật vậy, swing(n) luôn là số nguyên.

Vậy swing(n) có gì đặc biệt? Các thuật toán nhân nâng cao sẽ chỉ hoạt động tốt khi hai thừa số có độ lớn tương đương nhau. Vì vậy, chỉ tiếp cận n! là rất khó khăn.

Đặt e_p(n) là số mũ của thừa số nguyên tố p trong pt của n. Vậy e_p(swing(n)) = sigma((n/p^i) MOD 2). Khi đó ta có thể tính swing(n) bằng cách tính riêng từng thừa số một rồi chia để trị.

Bây giờ là làm sao để dùng lại swing(n DIV 2) :smiley: chứ bỏ hết thừa số 2 rất dễ khi bạn dùng biểu diễn nhị phân.

4 Likes

Không ai cần tính 1 tỉ giai thừa một cách chính xác cả, có phải đề là tính n! MOD M không?

3 Likes

Mình biết, nhưng mà thầy dạy môn thực hành của mình có ra đề này để kiểm tra bạn à

Bạn có thể nói kỹ hơn được không, sigma là hàm gì?

oops :smiley: e_p(swing(n)) = sigma(i=1…inf) (n DIV p^i MOD 2).

Do e_p(a/b) = e_p(a) - e_p(b)
nên

e_p(swing(n)) = e_p(n!) - 2*e_p((n DIV 2)!)
= sigma(i=1..) (n DIV p^i)  - 2*sigma(i=1..) (n DIV 2 DIV p^i)
= sigma(i=1..) (n DIV p^i - 2 * n DIV p^i DIV 2) (*)

mà a MOD b = a - a DIV b * b (định nghĩa phép chia) nên suy ra đpcm.

(*): Với b, c nguyên >= 2:
a/b/c = a/c/b <=> (a DIV b + eps1) / c = (a DIV c + eps2) / b với 0 <= eps1, eps2 < 1
<=> a DIV b / c + eps1 / c = a DIV c / b + eps2 / b
<=> a DIV b DIV c + e1 = a DIV c DIV b + e2
Ta có e2, e1 < 1 nên rút phần nguyên suy ra a DIV b DIV c = a DIV c DIV b.

n DIV (a*b) =? n DIV a DIV b.


Và tại sao hai thừa số phải có số chữ số tương đương (chênh nhau khoảng vài lần là tối đa)? Karatsuba, Toom-Cook và FFT đều là chia để trị. Khi thừa số đủ nhỏ thì ta đặt tính bt O(n^2) sẽ nhanh hơn, nhưng với chênh lệch lớn thì gộp lại cả quá trình thì số phép nhân kiểu này là quá nhiều.
Chữ số không nhất thiết phải theo hệ thập phân, mà nhanh nhất là 2^32-phân & dễ code nhất là 10^9-phân.

3 Likes

:joy:

using System.Numerics.BigInteger;
3 Likes

^ lắc đầu :smiley: chỉ cài sẵn O(n^2) thôi.

1 Like

O(n) loop 1 tỷ thì đã là một chuyện khó
cứ coi như đủ thời gian để chờ đợi thì kết quả của nó ghi ra file text thuần cũng nặng vài GB
đề bài tập này chẳng có gì thực tế cả, khè sv là chính\

nếu là kiểm tra trên giấy thì cứ loop với array mà phang thôi

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?