Phân tích thừa số nguyên tố: Thuật toán Pollard's Rho O(N^(1/4))

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

• Hiểu nghịch lý ngày sinh nhật (Birthday Paradox) làm cơ sở cho thuật toán Pollard's Rho: xác suất tìm được hai số x, y sao cho gcd(|x - y|, N) > 1 sau khoảng O(N^1/4) bước lặp.
• Sử dụng hàm đa thức giả ngẫu nhiên f(x) = (x² + c) mod N và thuật toán phát hiện chu trình Floyd hoặc Brent.
• Kết hợp với Miller-Rabin để đệ quy phân tích triệt để một số lớn 10¹⁸ thành tích các thừa số nguyên tố.

Mô tả bài toán

Cho một số nguyên dương N (2 ≤ N ≤ 10¹⁸). Hãy tìm tất cả các thừa số nguyên tố của N và in ra theo thứ tự tăng dần (nếu một thừa số xuất hiện nhiều lần thì in tương ứng bấy nhiêu lần).

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

• 2 ≤ N ≤ 10¹⁸.
• Thời gian: 1000ms. Bộ nhớ: 256MB.