Lũy thừa

Xem dạng PDF

Gửi bài giải

Điểm: 1,04 (OI)
Giới hạn thời gian: 4.5s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VOS Round 28
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Benjamin là một cậu học sinh rất giỏi toán và rất hay ham học hỏi. Ở lớp Benjamin luôn là người đặt ra những câu hỏi học búa cho thầy cô và cả bạn bè. Dĩ nhiên là cậu cùng thường xuyên đưa ra những vấn đề và tự mình giải quyết.

Một hôm, sau khi học về cách tính biểu thức ~A^{T}~, cậu liền nghĩ ra một vấn đề đó là có cách nào tính nhanh ~A^{T}~ và lập tức cậu nghĩ ra hướng giải quyết.

Nhưng vẫn không dừng ở đó cậu tự hỏi nếu có ~M~ số ~T_{1}~, ~T_{2}~, ...~T_{M}~ thì có cách nào tính nhanh được biểu thức ~F(T_{1})~ ~+~ ~F(T_{2})~ ~+~ ...~+~ ~F(T_{M})~ hay không và mất nhiều ngày sau đó Benjamin mới nghĩ ra cách làm. Sau khi ra cách làm Benjamin liền lên VNOI đố các VNOI_er giải bài toán trên :D. Biết rằng ~F(x)~ ~= A^{x}.~

Input

  • Gồm một dòng chứa ~7~ số ~M~, ~A~, ~a~, ~b~, ~c~, ~d~, ~BASE~.
  • ~T_{1} = a~.
  • ~T_{i} =~ ~(T_{i-1} \times b + c)~ mod ~d~.

Output

  • Gồm một dòng chứa kết quả bài toán mod cho BASE.

Giới hạn

  • ~M \le 2 \times 10^{7}~.
  • ~A~, ~d \le 10^{12}~.
  • ~BASE \le 10^{9}~.
  • ~a~, ~b~, ~c \le 10^{5}~.
  • ~40\%~ số test, ~M \le 10^{5}~.
  • ~M~, ~A~, ~a~, ~b~, ~c~, ~d > = 1~.

Sample Input

1 8 1 1 1 1 2

Sample Output

0

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.