Lũy thừa nhiều lần
Xem PDF
Điểm:
250
Thời gian:
0.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Các bạn học sinh tại trường tiểu học L làm bài quá nhanh chóng, hiện tại đang đòi một bài tập thử thách hơn. Nên tôi bảo các bạn ấy tính cái này. Cho số \(X = (\cdots ((a_1^{a_2})^{a_3})^{a_4} \cdots )^{a_n}\). Sau khi đem \(X\) chia lấy dư cho \(2004010501\) thì được kết quả là bao nhiêu?.
Nói cách khác, bạn được cho dãy \(a\) gồm \(n\) số nguyên dương lớn hơn \(1\). Bạn lấy số thứ nhất lũy thừa cho số thứ hai, xong lại lấy kết quả đem đi lũy thừa cho số thứ ba, rồi lại lấy kết quả đem đi lũy thừa cho số thứ tư, ..., cứ như thế cho tới số cuối cùng.
Ơ nhưng đây là bài tập của mấy bạn ấy mà, sao các bạn lại phải code nhỉ? Dù sao cũng lỡ rồi nên các bạn cứ làm đi nhé.
Input
- Dòng đầu chứa số \(n\), \(1 \le n \le 10^6\).
- Dòng tiếp chứa \(n\) số nguyên dương, trong đó \(1 < a_i \le 10^{18}\)
Output
- Gồm một dòng duy nhất chứa kết quả
Example
Test 1
Input
4
2 3 4 5
Output
838811359
Note
- \(2^3 = 8, 8^4 = 4096, 4096^5 = 1152921504606846976\), số này đem chia dư được kết quả \(838811359\).
Bình luận
Hint
\(\left( \cdots \left( \left( a_1^{a_2} \right)^{a_3} \right)^{a_4} \cdots \right)^{a_n}\) = \(a_1^{(a_2 \cdot a_3 \cdot a_4 \cdots a_n)}\)
Và với số mod là nguyên tố, ta có thể áp dụng phi hàm Euler: \(a^b \mod p \equiv a^{(b \mod \phi(p))} \mod p\)
Đọc đề xong xỉu, chưa làm nhưng khả năng time out là hầu như ko thể tránh khỏi ;-;