Bedao Regular Contest 03 - 3 NUMBERS

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.



  • 31
    nmhienbn   commented on Nov. 29, 2021, 3:08 p.m. edit 11

    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})~

    ~\sum\limits_{i=1}^{n} \tau(n) = 2 \times \sum\limits_{i=1}^{\lfloor \sqrt{n} \rfloor} \Big\lfloor \frac{n}{i} \Big\rfloor - \Big\lfloor \sqrt{n} \Big\rfloor ^2 ~

    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]~


    • 4
      Lulili   commented on Dec. 1, 2021, 3:42 p.m.

      cảm ơn anh đã viết thêm cách làm cho bài này ạ <3


    • 2
      lmhieu   commented on Nov. 29, 2021, 3:40 p.m.

      cảm ơn bạn nhiều ạ ^^