Sắp xếp theo Modul K (THTB - TP 2021)

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Từ dãy số tự nhiên \(1; 2; 3; ...; N\) người ta sắp xêp lại dãy số này theo số dư trong các phép chia các số hạng của dãy số cho một số lự nhiên \(K\) là ước nào đó của \(N\) như sau:

  • Đoạn thứ nhất gồm tất cả các số chia hết cho \(K\);
  • Đoạn thứ hai gồm tất cả các sổ chia \(K\) dư 1;
  • Đoạn thứ ba gồm tất cả các số chia \(K\) dư 2;
  • ...
  • Đoạn cuối cùng gồm tất cà các số chia \(K\)\(K\) - 1.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiêu tăng dần.

Ví dụ: Với \(N = 12\)\(K = 4\) sau khi sắp xếp ta có dãy số sau: \(4; 8; 12; 1; 5; 9; 2; 6; 10; 3; 7; 11\)

Yêu cầu: Cho trước 3 số nguyên dương \(N; K; M\) (với \(K\) là ước của \(N\)\(M < N\)). Tìm số hạng thử \(M\) của dãy đã sắp xếp.

Dữ liệu

  • 3 số nguyên dương \(N; K; M\) (\(N \le 10^{16}; K \le 10^9; K\) là ước của $N; M < N) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Kết quả

  • Ghi ra số hạng thứ M của dãy số theo yêu cầu.

Input

12 4 6

Output

9

Giới hạn

  • Có 20% test ứng với \(N \le 10^2\);
  • Có 30% test ứng với \(10^2 < N \le 10^6\);
  • Có 30% test ứng với \(10^6 < N \le 10^9\);
  • Có 20% test ứng với \(10^9 < N \le 10^{16}\).

Nguồn: THTB - Cấp TP 2021.


Bình luận

Không có bình luận nào.