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

    solution

    Đề bài: [Giải thuật] Hàm Euler phi

    Cho số nguyên nnn. Hãy tính giá trị hàm Euler phi φ(n)\varphi(n)φ(n) — số lượng số nguyên trong [1,n][1, n][1,n] nguyên tố cùng nhau với nnn.

    • Đị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:

      In một số nguyên: φ(n)\varphi(n)φ(n).

    Ví dụ:

    Đầu vào:

    12

    Đầu ra:

    4

    Giải thích:

    Các số nguyên tố cùng nhau với 12 trong [1,12] là 1,5,7,11 -> phi(12)=4.

    Đang tải editor...