Bedao Regular Contest 03 - 3 NUMBERS
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Đếm số lượng bộ số ~(a, b, c)~ nguyên dương sao cho ~a \times b \times c \le n~.
Lưu ý: Bộ ~(1, 2, 3)~ vẫn tính là khác so với ~(1, 3, 2)~ hay ~(3, 2, 1)~.
Input
Gồm ~1~ dòng chứa số nguyên dương ~n~. ~(1 \le n \le 10^{9})~
Output
In ra số lượng bộ ba số ~(a, b, c)~ thỏa mãn đề bài.
Sample Input
3
Sample Output
7
Giải thích
Có các bộ ~3~ số là ~(1,1,1), (1,1,3), (1,3,1), (3,1,1), (1,1,2), (1,2,1), (2,1,1)~
Subtask
- ~40\%~ số test có ~1 \le n \le 100~
- ~60\%~ số test còn lại không có điều kiện gì thêm
Bình luận
WOW, bài 4 thật sự là một bài hay. Và mình đã tìm ra 1 solution bằng Số học (Number Theory) từ năm 2011 của Andrew Lelechenko: (Đây không phải lời giải chính thức và khá phức tạp)
"To compute ~a_n~ for huge ~n~ in sublinear, use ~a_n = 3*\sum\limits_{i=1}^{n_3} \bigg( \sum\limits_{j=1}^{\Big\lfloor \frac{n}{i} \Big\rfloor} \tau(j) - \sum\limits_{j=1}^{n_3} \Big\lfloor \frac{n}{i*j} \Big\rfloor \bigg) + n_3^3~, where ~n_3 = \Big\lfloor \sqrt[3]{n} \Big\rfloor~." - Andrew Lelechenko, Apr 15 2011 (Source)
Và hàm ~\tau(n)~ là hàm đếm số ước của ~n~. và ~\sum\limits_{j=1}^{n} \tau(n)~ có cách tính trong ~O(\sqrt{n})~
Với cách giải này, ĐPT có lẽ là ~O(\sqrt[6]{n^5})~. Nhưng vì đây là 1 bài toán số học nên ĐPT có thể nhỏ hơn.
* Giải thích với 1 số bạn: ~\lfloor x \rfloor~ là kí hiệu phần nguyên, hay số nguyên lớn nhất không vượt quá ~x~ của quốc tế. Có thể các bạn đang quen dùng ~[x]~
cảm ơn anh đã viết thêm cách làm cho bài này ạ <3
cảm ơn bạn nhiều ạ ^^