Counting Divisors (CSES FI)

Bach_Long · August 2, 2023, 6:33am

Đây là link đề: https://cses.fi/problemset/task/1713

VÀ ĐÂY LÀ CODE CỦA EM:

https://cses.fi/paste/9633ccd95d482e4965a0b2/

Vậy cho em hỏi phải dùng thuật toán nào mới AC được ạ, thuật em có ĐPT là O(10^8) cho trường hợp xấu nhất. Em có lên youtube xem và có một thuật tính tổng ước bằng cách phân tích ra thừa số nguyên tố rồi nhân tất cả số mũ của thừa số sau khi đã cộng thêm 1 với nhau, cũng có ĐPT là O(10^8) nhưng code lại AC, em cũng thử code lại y chang nhưng lại không AC :))) video đó cũng khá lâu, vào 2 năm trước r, hay do máy chấm của trang giờ đã yếu hơn trước ?? Mong các anh giải đáp thắc mắc, em cảm ơn ạ.

- CODE LẠI VIDEO TRÊN YOUTUBE: https://cses.fi/paste/860c99d2a9c22a3765b5e4/
nhưng bị TLE 2 test
- VIDEO YOUTE: https://www.youtube.com/watch?v=HEOBF_8F640

Ryu_Lch · August 2, 2023, 7:40am

Đây là code của mình. Cũng không thấy khác ý tưởng của bạn là mấy n AC phát một mà nhỉ

Mình có thấy bạn dùng mảng check gì đó chưa hiểu mục đích lắm. Nhưng mà để làm gì nhỉ. Có thể tại nó mà bạn chưa AC ?

:") với hơi tò mò chút trang này là gì thế có vẻ không phải là của VN

Bach_Long · August 2, 2023, 8:05am

à trang này của Phần Lan thì phải, mình dùng mảng check để lưu lại mấy số đã tìm được ước rồi thôi =)) mà hồi trước mình cũng thử bỏ cái đó cũng k AC, cảm ơn bạn để mình thử lại

hoặc do máy mình yếu quá :))))

noname00 · August 2, 2023, 8:10am

Code O(n \sqrt{x} \log{x}) thì TLE là phải rồi bạn. Hàm sqrt(x) trông thế thôi nhưng cũng tốn O(\log x) cho việc tính toán, chưa kể ở mỗi lần check điều kiện bạn lại gọi hàm sqrt(x) một lần nữa.

Bài này cải tiến sàng nguyên tố Eratosthenes một chút, check[x] thay vì lưu trạng thái là/không là số nguyên tố thì bây giờ lưu ước nguyên tố nhỏ nhất của x.

rogp10 · August 2, 2023, 1:48pm

Còn có khả năng test lớn hơn nên TLE.

Độ phức tạp của phân tích thừa số nguyên tố phụ thuộc vào thừa số nguyên tố lớn thứ hai của số đó là chính (tính luôn cả lũy thừa), nên sẽ nhanh hơn chia tới \sqrt{n}.