TLE-oj Cup Round 2 - GCD tổng tích
Xem PDF
Nộp bài
Điểm:
1400 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
128M
Input:
GCDSPR.inp
Output:
GCDSPR.out
Tác giả:
Dạng bài
Bạn được cho một số nguyên p. Ban đầu p=1, bạn phải thực hiện q truy vấn, mỗi truy vấn có dạng sau:
- + w: tăng số p lên w đơn vị, lưu ý w có thể âm.
- * w: nhân số p cho w.
Với mỗi truy vấn, bạn cần in ra giá trị gcd(p, a) với a là một số nguyên dương cho trước.
Input, Output và Subtasks
Input (GCDSPR.inp)
- Dòng đầu tiên gồm hai số nguyên dương a, q (a\le 10^{18}, q \le 10^5).
- q dòng tiếp theo, dòng thứ 1 + i gồm một ký tự c_i và số nguyên w_i (|w_i| \le 10^{18}, mô tả một truy vấn.
Output (GCDSPR.out)
- Gồm q dòng, mỗi dòng là kết quả của mỗi truy vấn.
Subtasks
- Subtask 1 (5\%): c_i = + và q, |w_i| \le 10^4.
- Subtask 2 (5\%): c_i = + và |w_i| \le 10^9.
- Subtask 3 (10\%): a | w_i (a là ước của w_i).
- Subtask 4 (10\%): |p| \le 10^{18} sau mọi truy vấn.
- Subtask 5 (15\%): c_i = *.
- Subtask 6 (15\%): c_i = +.
- Subtask 7 (20\%): a \le 10^9.
- Subtask 8 (20\%): Không có giới hạn gì thêm.
Sample
Input (GCDSPR.inp)
12 5
* 2
+ 1
* 2
* 4
+ -4
Output (GCDSPR.out)
2
3
6
12
4
Notes
- Ban đầu p = 1.
- Sau khi thực hiện truy vấn đầu tiên, p = 2, gcd(2, 12) = 2.
- Sau khi thực hiện truy vấn thứ hai, p = 3, gcd(3, 12) = 3.
- Sau khi thực hiện truy vấn thứ ba, p = 6, gcd(6, 12) = 6.
- Sau khi thực hiện truy vấn thứ tư, p = 24, gcd(24, 12) = 12.
- Sau khi thực hiện truy vấn thứ năm, p = 20, gcd(20, 12) = 4.
Bình luận