Mọi người có thể cho mình một số hướng đi cho các bài toán OLP liên quan đến số liệu lớn trong C++ được không ạ. Ví dụ như bài tập mình làm là:
Cho số nguyên n, k ( n<= 10^18, k<=10^12). Tìm m lớn nhất sao cho n! chia hết cho k^m.
Mình đã dùng phân tích thành tích các thừa số nguyên tố nhưng không dùng được với các số quá lớn. Cảm ơn các bạn đã giúp đỡ.
Tìm m lớn nhất sao cho n! chia hết cho k^m
Bài này không phải xử lí số lớn, mà bài này dùng 100% số học.
Mình gợi ý cho bạn cách phân tích TSNT hiệu quả:
Tạo dãy các số nguyên tố từ 1 -> 10^6. 2 trường hợp xấu nhất xảy ra khi phân tích TSNT là:
-
k = a * b(a là phần đã phân tích TSNT, b nguyên tố nằm ngoài khoảng [1, 10^6])
Kiểu gì thì kiểu, k cũng phải có 1 ước nguyên tố trong khoảng [1, 10^6] (vì giới hạn k <= 10^12 nên điều này chứng minh được). Sau khi chạy vòng for các số nguyên tố và chia k cho những ước nguyên tố (tính cả trùng nhau) mà còn lại 1 số nguyên lớn, ta chắc chắn số đó là số nguyên tố. Điều này cũng chứng minh được.
- k nguyên tố
Kiểm tra tính nguyên tố của nó rất dễ: xem có số nguyên tố nào trong khoảng từ 1 -> sqrt(k) xem có là ước của k hay không. Nếu không thì chắc chắn k nguyên tố, khỏi phân tích.
Mà lực lượng số nguyên tố trong khoảng [1, 10^6] chỉ khoảng 79k, chạy sẽ đỡ tốn thời gian rất nhiều.
2 Likes
Nếu bạn làm hàng loạt theo query thì sàng trước để đó là đúng. Nếu không thì dùng nhảy 6 hoặc 30.
2 Likes
mình cũng dùng sàng đến 2*10^6 rồi bạn, chỉ mắc đoạn số n nó lớn mà chia từng thừa số nguyên tố lần lượt thì mảng khai báo của mình nó không đủ.
Thực ra vấn đề nằm ở bên k^m chứ không nằm ở n!. Cần nhìn nhận rằng n! phải có những thừa số nguyên tố mà k có, chứ k^m không cần những thừa số của n!. Đó là tính bất đối xứng của quan hệ chia hết.
2 Likes
Anh có thể nói rõ thuật toán hơn nữa được không ạ.
DNH có chức năng quote cmt tự động, không cần phải copy paste lại đâu.
Bạn đang hiểu như thế nào? Mình đã trình bày thuật toán khá rõ rồi.
Khi mình lấy k chia cho các thừa số nguyên tố và tìm được ước số nguyên tố của nó. vậy sao mình tìm được m lớn nhất
Ví dụ: N = 6 và k = 6 thì N có 2 thừa số nguyên tố là 2, 3 vậy làm sao biết lấy 2
Bạn thử đọc link này:
http://vnoi.info/forum/5/5128/#post-6198
Mình thấy thớt khúc mắc ở phần phân tích TSNT nên mình mới đưa thuật phân tích TSNT cho thớt thôi.
Nếu k nguyên tố thì dùng công thức trunc(n/k) + trunc(n/k^2) + … vì k nguyên tố thì ko đếm sót được 
Ngược lại thì (ví dụ) một số góp vào thừa số 3, số còn lại góp thừa số 2, 3*2 = 6 nên sẽ đếm thiếu. Vậy ta phân tích k ra TSNT rồi giải bài toán trên với từng thừa số một (tức là p^e ấy), lấy min của các kết quả thu được làm đáp số cuối cùng.[spoiler]
Thực ra tính bất khả phân (chỉ chia hết cho 1 và chính nó) là chưa đủ để một số là số nguyên tố. Ở câu thứ hai đã áp dụng định nghĩa nguyên tố p | ab <=> p | a && p | b.[/spoiler]
2 Likes
cách này hay v, cho mk lý thuyết câu đầu tiên của bạn ở đâu v, mk chưa hiểu lắm
Từ 1 đến n có \left\lfloor \frac{n}{p} \right\rfloor số chia hết cho p (p, 2p, 3p, ...\left\lfloor \frac{n}{p} \right\rfloor p)
1 Like
Nhưng mà sao lại có công thức này: trunc(n/k) + trunc(n/k^2) + …, mk hiểu mỗi cái trunc(n/k)\
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?