Tìm M Lớn Nhất Sao Cho N! Chia Hết Cho K^m - Programming

Có thể bạn quan tâm

programmingalgorithm khongloithoatkt (Tăng Văn Phương) January 27, 2018, 1:40pm #1 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 đỡ. noname00 (HK boy) October 26, 2017, 8:20am #2 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 rogp10 (rogp10) October 26, 2017, 9:26am #3 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 noz1995 (Trần Hoàn) October 26, 2017, 10:26am #4 Đây là sàng: https://primes.utm.edu/lists/small/100000.txt2 Likes khongloithoatkt (Tăng Văn Phương) October 26, 2017, 10:38am #5 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 đủ. rogp10 (rogp10) October 26, 2017, 10:53am #6 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 longho (Chung) March 13, 2021, 3:56pm #8 Anh có thể nói rõ thuật toán hơn nữa được không ạ. noname00 (HK boy) January 27, 2018, 1:30am #9 DNH có chức năng quote cmt tự động, không cần phải copy paste lại đâu.

Anh có thể nói rõ thuật toán hơn nữa được không ạ.

Bạn đang hiểu như thế nào? Mình đã trình bày thuật toán khá rõ rồi. longho (Chung) January 27, 2018, 1:38am #10 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 noname00 (HK boy) January 27, 2018, 2:09am #11 Bạn thử đọc link này:http://vnoi.info/forum/5/5128/#post-6198Mì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. rogp10 (rogp10) January 27, 2018, 5:27am #12 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 Sang_Nguyen_Van (Sang Nguyễn Văn) March 13, 2021, 11:06am #13 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 rogp10 (rogp10) March 13, 2021, 2:12pm #14 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 Sang_Nguyen_Van (Sang Nguyễn Văn) March 14, 2021, 7:16am #15 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)\