Extended Baby-Step Giant-Step: Logarithm rời rạc tổng quát

Mô tả bài toán

Cho ba số nguyên dương A, B, M.

Tìm số nguyên không âm x nhỏ nhất thỏa mãn phương trình đồng dư: A^x ≡ B mod M Lưu ý quan trọng: A và M không nhất thiết nguyên tố cùng nhau (gcd(A, M) > 1).

Yêu cầu: Tìm số nguyên không âm x nhỏ nhất thỏa mãn. Nếu không tồn tại x, in ra -1.

Dữ liệu vào

• Dòng đầu chứa số lượng bộ test T (1 ≤ T ≤ 20).
• T dòng tiếp theo, mỗi dòng chứa ba số nguyên A, B, M (1 ≤ A, B, M ≤ 10⁹).

Dữ liệu ra

• Với mỗi bộ test, in ra giá trị x nhỏ nhất tìm được, hoặc -1 nếu vô nghiệm.

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

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.