VM 08 Bài 08 - Kiến

Xem dạng PDF

Gửi bài giải


Điểm: 0,20 (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:
VNOI Marathon '08 - Round 11/DivBProblem Setter: Ngô Minh Ðức
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Họ nhà kiến tổ chức một trò chơi như sau để mừng năm mới. Những chú kiến quây thành một vòng tròn. Kiến chúa sẽ đưa ra một con số và gọi nó là số ~M~. Bắt đầu, kiến chúa đếm số ~1~, theo chiều kim đồng hồ, các chú kiến lần lượt đếm số tiếp theo. Đến lượt chú kiến đếm phải số đúng bằng số ~M~ thì sẽ phải đi ra khỏi vòng tròn. Việc đếm lại từ ~1~ bắt đầu từ chú kiến tiếp theo, theo chiều kim đồng hồ.

Trò chơi kết thúc, khi chỉ còn lại một chú kiến. Chú kiến đó sẽ nhận được món qùa đầu năm của họ nhà kiến.

Biết số chú kiến ban đầu trên vòng tròn và số ~M~. Hãy xác định số thứ tự của chú kiến sẽ nhận được phần thưởng may mắn. Các chú kiến được đánh số thứ tự theo chiều kim đồng hồ, bắt đầu từ kiến chúa có số hiệu ~1~.

Input

Dòng 1: chứa số nguyên dương ~N~, là số chú kiến trên vòng tròn.

Dòng 2: chứa số nguyên dương ~M~.

Giới hạn:

  • ~1 \le N \le 10^{12}~, ~3 \le M \le 10^6~.
  • ~M \le N~.

Output

Gồm 1 dòng duy nhất, chứa số thứ tự của chú kiến sẽ nhận được món qùa đầu năm

Sample Input

7
3

Sample Output

4

Note

Thứ tự những chú kiến phải ra khỏi vòng tròn lần lượt là: ~3~ ~6~ ~2~ ~7~ ~5~ ~1~.

Chú kiến ~4~ là chú kiến may mắn!


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    Thangdeptrai  đã bình luận lúc 19, Tháng 6, 2023, 19:35

    Ai giải thích cho mình cthuc bài này đk ạ?


    • 0
      OrzSeaPosjtive  đã bình luận lúc 20, Tháng 6, 2023, 1:59

      bạn tìm hiểu bài toán josephus nhé