Submit solution
Points:
1.50 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem types
Phát đang phải hoàn thành bài tập cuối kì của mình, bài toán của Phát như sau.
Cho một bánh xe của 3 số nguyên ~A, B, C~, và một số ~M~ là số nguyên tố, bánh xe có ~N~ lần xoay, trước mỗi lần xoay, Phát sẽ tính ~X~ kết quả của phép toán ~{A^B}^C~ sau đó lấy kết quả sau khi chia phần dư cho ~M~. Sau đó với mỗi lần xoay, Phát sẽ hoán đổi vị trí ~A \rightarrow B,\ B \rightarrow C,\ C \rightarrow A~, sau đó tiếp tục thực hiện các thao tác trên cho tới khi hoàn thành ~N~ lần xoay.
Bài toán kết thúc bằng ~Q~ câu trả lời, mỗi câu hỏi gồm 2 số ~L, R~ yêu cầu bạn trả lời trong phép xoay thứ ~L~ tới phép xoay thứ ~R~ tổng ~X~ của tất cả các phép xoay này là bao nhiêu ?
Input
- Dòng đầu tiên gồm 2 số ~N, M, Q~ được phân tách nhau bởi dấu cách ~(1 \leq N \leq 3 \times 10^5,\ 1 \leq M \leq 10^9,\ 1 \leq Q \leq 10^5)~.
- Dòng tiếp theo gồm 3 số nguyên ~A, B, C~ ~(1 \leq A, B, C \leq 10^9)~.
- ~Q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~L, R~ ~(1 \leq L \leq R \leq N)~.
Output
- Gồm ~Q~ dòng trả lời từ phép xoay thứ ~L~ đến phép xoay thứ ~R~ tổng của các ~X~ là bao nhiêu.
Sample
Input #1
10 37 3
36 29 98
1 10
5 8
4 4
Output #1
225
64
36
Comments
My solution:
solution bạn này hay nè dễ hiểu hơn.
bạn nói đúng đấy, mình thấy solution này cũng dễ hiểu.
cách này a thấy đúng dễ hiểu hơn nma cài đặt a thấy phưucs tạp hơn, fermat nhỏ khó hiểu hơn nma cài dễ hơn :v
rất cảm ơn về đóng góp của e, ngoài ra solution của bài này còn có một cách khác sử dụng định lý Fermat nhỏ nữa nhé e có thể đọc thêm tại đây. hoặc ở editorial chính thức nhé !