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] Kiểm tra g có phải căn nguyên thủy

    g có sinh toàn bộ nhóm không?

    Cho p nguyên tố và g, hãy kiểm tra g có phải căn nguyên thủy modulo p hay không (bậc của g bằng p-1).

    Ví dụ

    p = 7, g = 3 → YES; p = 7, g = 2 → NO (bậc 3 ≠ 6).

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

      Hai số nguyên p g.

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

      p nguyên tố, 3 ≤ p ≤ 10^9, 1 ≤ g < p.

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

      YES nếu g là căn nguyên thủy, ngược lại NO.

    Ví dụ:

    Đầu vào:

    7 3

    Đầu ra:

    YES

    Giải thích:

    Bậc của 3 mod 7 là 6 = p-1 nên là căn nguyên thủy: YES.

    Đang tải editor...