HSPC14D - Đội mũ
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Từ xưa đến nay, việc phân chia học sinh vào từng khoa của trường Hogwart được thực hiện bởi những chiếc mũ phép thuật. Trước kia, trường có 4 khoa. Tuy nhiên, sau khi tái cơ cấu lại trường, số khoa thay đổi thành p. Những chiếc mũ vẫn được sử dụng để phân chia học sinh.
Kế hoạch phân chia học sinh vào từng khoa được biểu diễn bằng dãy số a[1], a[2],..., a[k], trong đó a[i] là khoa mà học sinh i sẽ học. Cách phân chia học sinh của chiếc mũ được mô tả như sau: Các khoa trong trường được đánh số từ 0 đến p – 1. Gọi next(x) là khoa kế tiếp của khoa x với next(x) = x+1 với x < p -1 và next(p-1)= 0. Kế hoạch phân chia được bắt đầu bằng một dãy số có duy nhất 1 phần tử 0. Sau mỗi bước, dãy a với k phần tử sẽ trở thành dãy số mới có 2k phần từ a[1], a[2],..., a[k], next(a[1]), next(a[2]),..., next(a[k]).
Xét ví dụ về việc phân chia 9 học sinh vào 4 khoa. Chiếc mũ sẽ thực hiện theo kế hoạch: (0), (0, 1), (0, 1, 1, 2), (0, 1, 1, 2, 1, 2, 2, 3), (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 0),... Độ dài của dãy cuối đủ cho 9 học sinh.
Cho các cặp số p, n. Nhiệm vụ của bạn là cho biết khoa nào trong số p khoa của trường mà học sinh thứ n sẽ vào học ở đó (học sinh được đánh số từ 1)
Từ xưa đến nay, việc phân chia học sinh vào từng khoa của trường Hogwart được thực hiện bởi những chiếc mũ phép thuật. Trước kia, trường có 4 khoa. Tuy nhiên, sau khi tái cơ cấu lại trường, số khoa thay đổi thành p. Những chiếc mũ vẫn được sử dụng để phân chia học sinh. Kế hoạch phân chia học sinh vào từng khoa được biểu diễn bằng dãy số a[1], a[2],..., a[k], trong đó a[i] là khoa mà học sinh i sẽ học. Cách phân chia học sinh của chiếc mũ được mô tả như sau: Các khoa trong trường được đánh số từ 0 đến p – 1. Gọi next(x) là khoa kế tiếp của khoa x với next(x) = x+1 với x < p -1 và next(p-1) = 0. Kế hoạch phân chia được bắt đầu bằng một dãy số có duy nhất 1 phần tử 0. Sau mỗi bước, dãy a với k phần tử sẽ trở thành dãy số mới có 2k phần từ a[1], a[2],..., a[k], next(a[1]), next(a[2]),..., next(a[k]). Xét ví dụ về việc phân chia 9 học sinh vào 4 khoa. Chiếc mũ sẽ thực hiện theo kế hoạch: (0), (0, 1), (0, 1, 1, 2), (0, 1, 1, 2, 1, 2, 2, 3), (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 0),... Độ dài của dãy cuối đủ cho 9 học sinh. Cho các cặp số p, n. Nhiệm vụ của bạn là cho biết khoa nào trong số p khoa của trường mà học sinh thứ n sẽ vào học ở đó (học sinh được đánh số từ 1.
Input
Dòng đầu là số truy vấn Q (1 ≤ Q ≤ 310000). Q dòng tiếp, mỗi dòng là một cặp số p, n (1 ≤ n ≤ 10^18 , 2 ≤ p ≤ 10^18 ).
Output
In ra Q dòng lần lượt là đáp án của Q truy vấn
Example
Input: 10 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 4 Output: 0 1 1 2 1 2 2 3 1 2
- Người up: beo_chay_so
- Nguồn bài: HSPC 2014