Logarithm rời rạc: Thuật toán Baby-step Giant-step O(sqrt(M))

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

• Hiểu bài toán Logarithm rời rạc: Tìm số nguyên không âm nhỏ nhất x sao cho A^x ≡ B mod M.
• Nắm vững thuật toán Baby-step Giant-step (BSGS) của Daniel Shanks:
• Đặt m = lceil √(M) rceil.
• Biểu diễn x = i · m - j với 1 ≤ i ≤ m và 0 ≤ j < m.
• Biến đổi phương trình thành (A^m)ⁱ ≡ B · A^j mod M.
• Tận dụng cấu trúc bảng băm (std::unordered_map hoặc sắp xếp hai con trỏ) để đạt độ phức tạp O(√(M)).

Mô tả bài toán

Cho 3 số nguyên dương A, B, M với M là số nguyên tố và gcd(A, M) = 1. Hãy tìm số nguyên không âm nhỏ nhất x thỏa mãn: A^x ≡ B mod M Nếu không tồn tại số x nào thỏa mãn, in ra -1.

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 ≤ A, B < M ≤ 10⁹.
• M là số nguyên tố.
• Thời gian: 1000ms. Bộ nhớ: 256MB.