LUTH2 - Lũy thừa 2
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Hôm nay An được thầy giáo giao cho một bài tập. Ông ấy yêu cầu An phải tính AB mod K, nhưng ông yêu cầu phải giải quyết bài toán với cả 2 trường hợp số mũ âm và dương. Đồng thời ông cũng đưa ra 2 giả thuyết sau để giúp bài toán trở nên đơn giản hơn:

 - A-B mod K ≡ (A-1 mod K)B mod K với B > 0.

 - A, K là 2 số nguyên tố cùng nhau.

Bài toán này quá khó so với An và cậu ta nhờ sự giúp đỡ của bạn, hãy giúp cậu ấy nhé.

Dữ liêu nhập: Dòng đầu tiên chứa một số nguyên T - số lượng test case (1 ≤ T ≤ 1000). T dòng tiếp theo, mỗi dòng chứa 3 số nguyên A, B, K (1 ≤ A ≤ 106, −106 ≤ B ≤ 106, 1 ≤ K ≤ 106)

Dữ liệu xuất: Gồm T dòng, mỗi dòng chứa một số nguyên dương duy nhất là kết quả AB mod K

Ví dụ

  • input
    3
    1 2 3
    3 4 2
    4 -1 5
    output
    1
    1
    4

Update:

Biểu thức "A-1 mod K" thuộc về một vấn đề nằm trong lý thuyết đồng dư là "nghịch đảo module" (Modular multiplicative inverse). Nó được mô tả như sau: cho 2 số nguyên a và n nguyên tố cùng nhau thì sẽ tồn tại duy nhất 1 và chỉ một số tự nhiên x (0 ≤ X < n) sao cho ax ≡ 1 (mod n) và x này được gọi là nghịch đảo của a theo module n. Kí hiệu x ≡ a-1 (mod n).

Theo đề bài mô tả thì A và K đều là số nguyên tố nên hiển nhiên 2 số này luôn nguyên tố cùng nhau.

Hiện tại theo mình biết thì có 2 cách giải bài này theo 2 công thức khác nhau. Có thể tham khải thêm tại đây

Back to Top