Tìm GCD
Xem PDFCho một tập hợp rỗng, bạn sẽ lần lượt thực hiện \(N\) thao tác. Có hai loại thao tác được thực hiện:
• Thao tác 1 có dạng \(1\) \(x\) : thêm số \(x\) vào tập hợp.
• Thao tác 2 có dạng \(2\) \(x\) : loại bỏ một số \(x\) ra khỏi tập hợp, dữ liệu luôn đảm bảo tồn tại ít nhất một số \(x\) trước khi thực hiện thao thao tác này.
Sau mỗi lần thực hiện thao tác, hãy đưa ra ước chung lớn nhất của tập hợp này. Với trường hợp tập hợp con rỗng hãy in ra số \(1\).
Input:
-
Dòng đầu tiên một số tự nhiên \(N(1 ≤ N ≤ 10^5)\).
-
\(N\) dòng tiếp theo, mỗi dòng là gồm 2 số \(t\) và \(x\) với \(t\) là loại thao tác và \(x\) là số cần được xử lí \((1 ≤ t ≤ 2, 1 ≤ x ≤ 10^9)\).
Output:
- Gồm \(N\) dòng là ước chung lớn nhất của tập hợp sau mỗi lần thực hiện một thao tác.
Test 1
Input
6
1 8
1 12
1 10
1 8
2 8
2 8Output
8
4
2
2
2
2Note
Tập hợp sau mỗi thao tác:
• Thao tác 1: 8 \(\rightarrow\) GCD = 8
• Thao tác 2: 8, 12 \(\rightarrow\) GCD = 4
• Thao tác 3: 8, 12, 10 \(\rightarrow\) GCD = 2
• Thao tác 4: 8, 12, 10, 8 \(\rightarrow\) GCD = 2
• Thao tác 5: 8, 12, 10 \(\rightarrow\) GCD = 2
• Thao tác 6: 12, 10 \(\rightarrow\) GCD = 2
Bình luận
$ Saygoodbye! $
Vãi cả dạng bài cày trâu :))
=))) Oh giờ em mới hiểu lí do em sai. Cay ghê
anh BiichSonNhat có vẻ thích LCM, GCD nhỉ ** 😕 **