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

    solution

    Đề bài: [Giải thuật] Tổng hàm Euler phi bằng sàng tuyến tính

    Hàm Euler φ(k)\varphi(k)φ(k) đếm số nguyên trong [1,k][1, k][1,k] nguyên tố cùng nhau với kkk. Cho nnn, hãy tính ∑k=1nφ(k)\sum_{k=1}^{n} \varphi(k)∑k=1n​φ(k). Dùng sàng tuyến tính để tính φ\varphiφ cho mọi số tới nnn trong O(n)O(n)O(n).

    Quy ước φ(1)=1\varphi(1)=1φ(1)=1.

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

      Một dòng: số nguyên nnn.

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

      0≤n≤5⋅1060 \le n \le 5\cdot10^60≤n≤5⋅106.

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

      Một số nguyên: ∑k=1nφ(k)\sum_{k=1}^{n}\varphi(k)∑k=1n​φ(k).

    Ví dụ:

    Đầu vào:

    5

    Đầu ra:

    10

    Giải thích:

    φ(1..5) = 1,1,2,2,4; tổng = 1+1+2+2+4 = 10.

    Đang tải editor...