LBC_2F - Mũ cực mạnh

View as PDF

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

Comments are disabled on this page.