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

Please read the guidelines before commenting.



  • 13
    DL_DinhVuMinhHung2k8  commented on Oct. 23, 2023, 1:43 a.m. edit 11

    My solution:

    Sử dụng mảng cộng dồn + thuật toán lũy thừa nhị phân

    Độ phức tạp O((3∗~10^5~)∗log2(max(a,b,c,m)))

    Ta nhận thấy rằng:

    Sau đúng 3 lần đổi a,b,c sẽ trở lại vị trí như ban đầu

    => Với mỗi lần đổi khác nhau ta chỉ cần tính a^(b^c) đúng 1 lần

    Chứng minh:

    Lưu ý: chỉ thay đổi giá trị a,b,c sau mỗi lần chứ thứ tự vẫn là không đổi nhé.

    Đứng đầu là a, thứ hai là b, thứ ba là c

    Vì mỗi lần đổi chỉ đổi giá trị và không đổi vị trí nên:

    Sau lần quay thứ 1: a=b, b=c, c=a => ta tính b^(c^a)

    => trước lần quay thứ 1 (lần thứ 0) ta tính a^(b^c)

    Sau lần quay thứ 2: b=c, c=a, a=b => c^(a^b)

    => trước lần quay thứ 2 (lần thứ 1) ta tính b^(c^a)

    Sau lần quay thứ 3: c=a, a=b, b=c => a^(b^c)

    => trước lần quay thứ 3 (lần thứ 2) ta tính c^(a^b);

    Tương tự với lần 4,5,6,...

    Từ đó => ta chỉ cần tính số lần xuất hiện của mỗi a^(b^c) khác nhau, sau đó ta chỉ cần nhân số lần xuất hiện với a^(b^c) tương ứng và cộng vào kết quả X.

    Cách thực hiện:

    Gọi x một số thuộc đoạn l,r (x>=l và x<=r)

    Bởi vì trước mỗi lần quay ta phải tính kết quả để công vào X nên:

    Khi x chia 3 dư 1 ta sẽ làm a^(b^c)

    Khi x chia 3 dư 2 ta sẽ làm c^(a^b)

    Khi x chia hết cho 3 ta sẽ làm b^(c^a)

    => Từ đó ta có thể đếm số lượng số chia 3 dư 1, chia 3 dư 2, chia hết cho 3 trong đoạn từ l đến r bằng mảng cộng dồn, sau đó ta có thể thực hiện mỗi truy vấn q với độ phức tạp O(1)

    my code: ideone

    Vì là lần đầu mình viết solution nên còn hơi bỡ ngỡ và sẽ khó tránh khỏi sai sót, nếu có bất kì lỗi nào hoặc chỗ nào không hiểu mong các bạn bình luận cho mình biết để có thể sửa đổi một cách nhanh nhất và đưa cho các bạn một solution chỉn chu nhất


    • -1
      vdtue  commented on Oct. 23, 2023, 10:27 a.m.

      solution bạn này hay nè dễ hiểu hơn.


      • -4
        Toanldyl1  commented on Oct. 23, 2023, 2:21 p.m.

        bạn nói đúng đấy, mình thấy solution này cũng dễ hiểu.


      • 1
        wronganswer  commented on Oct. 23, 2023, 1:45 p.m.

        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


    • 6
      wronganswer  commented on Oct. 23, 2023, 8:50 a.m. edited

      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é !