Siêu máy tính

Điểm: 7,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

17-18 DHBB K11

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Công ty Alpha giới thiệu siêu máy tính có khả năng thực hiện được tỉ tỉ phép toán trong vòng $1$ giây. Để chứng minh sức mạnh của siêu máy tính, công ty đã cho máy tính thực hiện một số lượng rất lớn các phép toán như sau:

Ban đầu, số $N$ được đặt giá trị bằng $1$ ;
Có t thao tác, mỗi thao tác thuộc một trong ba loại:
1. Nhân $N$ với $a^{b}$ ;
2. Chia $N$ cho $a^{b}$ (trong đó $a^{b}$ là ước của $N$ );
3. Tìm số hai số $p$ , $q$ mà $p^{q} = N$ và $q$ là lớn nhất, nếu $N = 1$ thì $p = 1, q = 1$ .

Công ty sẽ trao thưởng cho người nào kiểm chứng được kết quả mà siêu máy tính đưa ra. Ban giám khảo kỳ thi quyết định ra đề thi yêu cầu thí sinh viết chương trình nhận $t$ thao tác, nhưng với mỗi thao tác loại $3$ chỉ cần đưa ra hai số $p % M$ (phần dư của phép chia $p$ cho $M$ ) và $q$ .

Cho $M$ và $t$ thao tác, với mỗi thao tác loại $3$ hãy đưa hai số ra $p % M$ và $q$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương $M, t$ ( $M \leq 10^{9}$ );
Dòng thứ $i$ trong $t$ dòng tiếp theo mô tả thao tác thứ $i$ là một trong ba loại thao tác theo khuôn dạng: Bắt đầu số $k_{i}$ ( $k_{i}$ bằng $1$ hoặc $2$ hoặc $3$ ). Nếu là thao tác loại $1$ và loại $2$ thì tiếp theo là hai số nguyên dương $a_{i}, b_{i}$ ( $a_{i}, b_{i} \leq 10^{6}$ ).

Dữ liệu ra

Gồm một số dòng, mỗi dòng chứa hai số $p % M$ và $q$ tìm được tương ứng với mỗi thao tác loại $3$ .

Ràng buộc

$M \leq 10^{9}$
$a_{i}, b_{i} \leq 10^{6}$
20% số test: $t \leq 100$ và số $N$ không vượt quá $10^{18}$ trong quá trình thực hiện dãy thao tác;
40% số test: $t \leq 100$ và số $N$ không vượt quá $10^{180}$ trong quá trình thực hiện dãy thao tác;
40% số test: $t \leq 10^{5}$ .

Ví dụ

Input	Output	Giải thích
100 4 1 36 2 3 2 3 2 3	6 4 12 2	Ban đầu $N = 1$ . Sau thao tác 1: $N = 1 \times 36^{2} = 1296$ . Thao tác 3: $1296 = 6^{4}$ , in $6 % 100 = 6$ và $4$ . Sau thao tác 2: $N = 1296 / 3^{2} = 144$ . Thao tác 3: $144 = 12^{2}$ , in $12 % 100 = 12$ và $2$ .

Bình luận

luongdinhdung

đã bình luận lúc 22, Tháng 6, 2025, 15:32

C, C#, C++, Java, Javascript, Kotlin, Pascal, PyPy, Python, Scratch