Tìm GCD

Xem PDF



Tác giả:
Dạng bài
Điểm: 200 Thời gian: 1.0s Bộ nhớ: 128M Input: bàn phím Output: màn hình

Cho 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\)\(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 8
Output
8
4
2
2
2
2
Note

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


  • 0
    BichSonNhat 9:51 p.m. 7 Tháng 7, 2020

    $ Saygoodbye! $


    • -3
      Lê_Gia_Khánh 4:28 p.m. 7 Tháng 7, 2020

      Vãi cả dạng bài cày trâu :))

      1 phản hồi

      • 1
        SPyofgame 2:43 p.m. 7 Tháng 7, 2020

        =))) Oh giờ em mới hiểu lí do em sai. Cay ghê


        • 3
          Kuroo 2:12 p.m. 7 Tháng 7, 2020

          anh BiichSonNhat có vẻ thích LCM, GCD nhỉ ** 😕 **