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

    solution

    Đề bài: [An toàn thông tin] Hàm Euler phi(n)

    Hàm Euler phi(n)

    Hàm Euler totient phi(n) đếm số nguyên trong [1, n] nguyên tố cùng nhau với n. Đây là đại lượng cốt lõi trong RSA: phi(n) = (p-1)(q-1).

    Công thức: nếu n = p1^a1 * ... * pk^ak thì phi(n) = n * prod( (pi - 1) / pi ).

    Ví dụ

    Input:
10
Output:
4

    Các số nguyên tố cùng nhau với 10 trong [1,10] là {1,3,7,9} nên phi(10) = 4.

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

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

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

      1 <= n <= 10^15

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

      In giá trị phi(n). Quy ước phi(1) = 1.

    Ví dụ:

    Đầu vào:

    10

    Đầu ra:

    4

    Giải thích:

    Các số {1,3,7,9} nguyên tố cùng nhau với 10 nên phi(10) = 4.

    Đang tải editor...