Hàm Euler φ(n) đếm số lượng số nguyên dương không vượt quá n và nguyên tố cùng nhau với n. Đây là thành phần bắt buộc khi sinh khóa RSA: với n=p⋅q (p,q nguyên tố), khóa bí mật được tính dựa trên φ(n)=(p−1)(q−1).
Cho một số nguyên dương n, hãy tính φ(n).
Một dòng duy nhất chứa số nguyên n (1≤n≤1012).
Một số nguyên duy nhất - giá trị φ(n).
Ví dụ:
Đầu vào:
1
Đầu ra:
1
Đầu vào:
2
Đầu ra:
1
Đang tải editor...