ƯCLN với bước nhảy 2

View as PDF



Time limit:
Scratch 3.0s

Author:
Problem type
Points: 100 Time limit: 0.5s Memory limit: 256M Input: stdin Output: stdout

Trong một giấc ngủ ngày, Rùa mơ thấy mình hiện đang đứng tại một vị trí số nguyên trên trục số tự nhiên và Rùa sẽ nhảy \(k\) lần tới phía trước. Cứ nhảy \(1\) lần, vị trí hiện tại của Rùa là \(x\) sẽ trở thành \(x+2\). Vốn dĩ ghét vận động, Rùa muốn thoát khỏi giấc mơ kinh hoàng này. Muốn thoát, Rùa buộc phải hét lên một số mà đó là Ước chung lớn nhất của tất cả vị trí mà Rùa đã đi qua. Các bạn hãy giúp Rùa thoát khỏi cơn mê này!

Cụ thể hơn, hãy tính số nguyên dương \(d\) lớn nhất, mà tất cả số trong dãy \(\{x, x+2, x+4, ..., x+2k\}\) đều chia hết cho \(d\).

Với \(x=2\)\(k=2\), ta có \(A=[2,4,6]\), và đáp án là \(2\).

Input

  • Một dòng duy nhất chứa hai số nguyên, lần lượt là \(x\)\(k\) \((0 \leq k < x \leq 10^9)\)

Output

  • Một dòng duy nhất chứa số nguyên \(d\) là đáp án.

Example

Test 1

Input
2 2
Output
2
Note

Với \(x=2,k=2\), ta có \(A=[2,4,6]\) thì số \(2\) là số lớn nhất mà \(\{2,4,6\}\) đều chia hết cho nó.

Test 2

Input
3 1
Output
1
Note

Với \(x=3,k=1\), ta có \(A=[3,5]\). Vì \(3\)\(5\) là hai số nguyên tố, nên \(d\) phải bằng \(1\).


Comments


  • 0
    weqd    5:27 p.m. 17 sep, 2023

    test hình như hơi yếu:v


    • -4
      obitidev    5:49 p.m. 28 jul, 2022

      mình không biết ý tưởng của mình có sai hay không, nhưng bạn chỉ cần tìm gcd của xx + 2 😶

      (ý tưởng trên đã được kiểm nghiệm)

      1 reply

      • -8
        minhtuanitk20    10:30 p.m. 25 sep, 2021 edited

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 27
          hongquanyl1    8:23 p.m. 4 sep, 2021

          Bài này hay quá và cũng dễ hiểu cho học sinh cấp 1,2;
          AI thấy đúng thì điểm danh nào 👇