Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Hạng của quan hệ chia hết

    Trên tập S={1,2,…,n}S = \{1, 2, \dots, n\}S={1,2,…,n} xét quan hệ "chia hết": aRb  ⟺  a∣ba \mathrel{R} b \iff a \mid baRb⟺a∣b (tức aaa là ước của bbb). Hạng của quan hệ là số cặp có thứ tự (a,b)(a, b)(a,b) thuộc RRR.

    Hãy đếm số cặp (a,b)(a, b)(a,b) với a,b∈Sa, b \in Sa,b∈S và a∣ba \mid ba∣b. (Cặp (a,a)(a,a)(a,a) cũng được tính.)

    • Định dạng đầu vào:

      Một dòng chứa số nguyên nnn.

    • Ràng buộc đầu vào:

      1≤n≤10121 \le n \le 10^{12}1≤n≤1012.

    • Định dạng đầu ra:

      Một số nguyên là hạng của quan hệ.

    Ví dụ:

    Đầu vào:

    3

    Đầu ra:

    5

    Giải thích:

    Cac cap $a\mid b$ voi $a,b\le3$: (1,1),(1,2),(1,3),(2,2),(3,3) -> hang = 5.

    Đang tải editor...