Mình đang làm một bài về kiểu tính (N!*X)mod M với 1<=N,X<=10^18, M=10^6+3. Biết là tính ((N!%M)x(X%M))%M nhưng khi tính N! mình chia nhỏ ra các thành phần mod cho M rồi nhân lại thì bị time limit error, không biết có cách nào tính nhanh hơn không, kiểu thêm đk để giới hạn số lần mod cho M ấy.
Tính N! mod M với N là số lớn
N >= M thì N! mod M = 0 rồi mà bạn, tính làm gì nữa :v
6 Likes
là sao bạn, mình hc lập trình mà chỉ hc đc lí nên mấy cái toán mình ko hiểu lắm, bạn giải thích kĩ giúp mình với
Ý ổng là lớn >=, vd 5>4 thì 5!=5.4.3.2 có 4 trong đó nên mod 4 =0, mà cái này 10^6 vẫn còn bé hơn 10! nên t nghĩ đến cái gt bé hơn 10^6 thì ta mod vẫn bằng chính nó nhưng trong khoảng vẫn kiểm soát còn hơn thì khỏi mod do nó bằng 0 rồi
Nếu N >= M thì N! có nhân tử M trong đó, tức là N! chia hết cho M nên mod của chúng = 0
2 Likes
Vừa mới nghĩ ra thì bạn rep luôn rồi :))))
8!<10^6<9! nên t nghĩ xét th từ 1->8 thì = chính nó, từ 8->10^6 thì <10^6, từ 10^6 trở đi thì =0 đc ko ta?
Từ 1->8 thì N! mod M = N!
Từ 9->10^18 thì N! mod M = 0
từ 9 tới M-1 thôi, có tính tới 10^18 đâu :V
2 Likes
Giới hạn của N là vậy mà a
vì N >= M thì N! chia hết cho M thì output ra 0 luôn tính làm gì nữa :V
nếu N < M thì mới tính, mà N < M thì làm gì N chạy tới 10^18 vì M = 10^6 + 3 mà :V 1 triệu phép nhân và chia lấy dư thì chắc chạy kịp thời gian :V
3 Likes
Thì ghi giới hạn ở đây là đang nói về toán học mà, chứ có phải về tin học đâu a
Code thì điều kiện if n > 8 thôi
cái này mình tạo mảng từ 0->M-1 mà trong mỗi phần tử A[N] chứa N! mod M để lúc nhập N mình lấy ra tính đc ko a?
em ghi N từ 9 tới 10^18 N! mod 1000003 = 0 là sao :V :V N >= 1000003 thì N! mod M mới = 0 chứ :V 9 <= N < 1000003 vẫn phải tính mà :V
2 Likes
Ok, sửa lại rồi đó a :))
Tạo một cái mảng từ 8 phần tử thôi bạn, chứa 1! 2! 3! … 8! là đủ rồi
Oof, cái này dành để tính n!
Ta có thể tính theo swing factorial.
BĐ: a DIV b DIV c = a DIV c DIV b
Ta c/m a DIV b DIV c = a DIV bc
Áp dụng định nghĩa phép chia cho a và bc, ta có: a = bcm + r_bc, 0 <= r_bc < bc
Tương tự a = bcm' + b*r_c + r_b, 0 <= r_b < b, 0 <= r_c <= c-1
suy ra m = m', xong.
Ta định nghĩa: swing(n) := n!/(n DIV 2)!^2, nó trông như nC(n DIV 2), và nó là số nguyên 
Kí hiệu e_p(n) là số mũ của thừa số p trong phân tích TSNT của n, ta có e_p(n!) = sigma(p^k <= n)(n/p^k).
Vậy e_p(swing(n)) = sigma(p^k <= n)(n DIV p^k - 2(n DIV 2) DIV p^k)
= sigma(p^k <= n) (n DIV p^k) MOD 2).
Ct truy hồi: n! = (n DIV 2)!^2 * swing(n), swing(1) = 1.
4 Likes
Tạo mảng để làm gì, trong khi tính 1 lần N! rồi thôi?
Mà sao lại có ý nghĩ tạo mảng từ 1! -> 9! làm gì @@ cuối cùng là để làm gì trong khi vẫn chỉ là tính N! @@
2 Likes
Bài nó vậy nè anh, em tính kiểu bình thường thì nó vẫn ra, nhưng khi nộp vào web của thầy để chấm thì lại time limit, nên e muốn hỏi cách làm nhanh hơn.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?