TLEoj Contest #08 - Fibonacci lũy thừa

Điểm: 200 (thành phần)

Thời gian: 3.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Ta định nghĩa $F_i$ là số fibonacci thứ $i$ với công thức như sau:

Nếu $i\le 2$ thì $F_i=1$
Ngược lại, $F_i=F_{i-1}+F_{i-2}$

Cho $q$ truy vấn, mỗi truy vấn gồm 4 số $a,b,c,M$ . Nhiệm vụ của bạn là phải tính $F_{a^b}\text{ }mod\text{ }F_c$ . Vì kết quả có thể rất lớn nên hãy xuất kết quả $mod\text{ }M$

Input, Output và Scoring

Input (bàn phím)

Dòng đầu tiên nhập số $q$ chỉ số truy vấn ( $1\le q\le 5\cdot 10^5$ )
Sau đó là $q$ dòng, mỗi dòng nhập 4 số $a,b,c,M$ ( $1\le a,b\le 10^{18},1\le c, M\le 10^9$ )

Output (màn hình)

Xuất ra $q$ dòng, dòng thứ $i$ xuất ra kết quả tương ứng của truy vấn thứ $i$

Subtasks

Subtask 1 $(5\%)$ : $a^b\leq 88$
Subtask 2 $(5\%)$ : $a^b\leq 10^{18},c\leq 88$
Subtask 3 $(10\%)$ : $c\leq 88$
Subtask 4 $(15\%)$ : $q\le 10^5$
Subtask 5 $(15\%)$ : $q\le 2\cdot 10^5$
Subtask 6 $(50\%)$ : Không có ràng buộc gì thêm.

Sample

Input (bàn phím)

4
3 3 3 10
3 3 5 10
3 3 5 2
4 16 15 300

Output (màn hình)

Notes

Trong truy vấn 1, ta có $F_{3^3}\text{ }mod\text{ }F_3=196418\text{ }mod\text{ }2=0$ , $0\text{ }mod\text{ }10=0$
Trong truy vấn 2, ta có $F_{3^3}\text{ }mod\text{ }F_5=196418\text{ }mod\text{ }5=3$ , $3\text{ }mod\text{ }10=3$
Trong truy vấn 3, ta có $F_{3^3}\text{ }mod\text{ }F_5=196418\text{ }mod\text{ }5=3$ , $3\text{ }mod\text{ }2=1$

Bình luận

Không có bình luận nào.