Kiểm tra số nguyên tố xác suất Miller-Rabin cho số lớn 10^18

Mục tiêu kiến thức

• Hiểu hạn chế của Định lý Fermat nhỏ (số giả nguyên tố Carmichael như 561).
• Nắm vững định lý căn bậc hai của đơn vị (Square root of unity) trên trường Z_p: Nếu x² ≡ 1 mod p thì x ≡ ± 1 mod p.
• Cài đặt Miller-Rabin tất định (Deterministic Miller-Rabin) cho số N < 2⁶⁴ chỉ bằng 7 cơ sở nguyên tố: {2, 325, 9375, 28178, 450775, 9780504, 1795265022}.

Mô tả bài toán

Cho T số nguyên dương N₁, N₂, …, N_T. Với mỗi số N_i, hãy kiểm tra xem số đó có phải là số nguyên tố hay không.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ T ≤ 10⁴.
• 1 ≤ N_i ≤ 10¹⁸.
• Thời gian: 1000ms. Bộ nhớ: 256MB.