trang chủ / đề bài / icpc23_nat_i

Dãy phân số vô hạn

Đề bài

Mô tả

Trong bài này, bạn cần trả lời T truy vấn. Mỗi truy vấn cho hai số n và k.

Xét dãy vô hạn các phân số p/q với 1≤p và 1≤q≤n (p, q nguyên). Các phân số này được sắp xếp tăng dần, ưu tiên theo giá trị p/q; nếu hai phân số có cùng giá trị thì phân số có tử số p nhỏ hơn đứng trước. Hãy tìm phân số nhỏ thứ k trong dãy này.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T (1≤T≤5000), số truy vấn. Mỗi dòng trong T dòng tiếp theo chứa hai số nguyên n và k (1≤n≤109, 1≤k≤1018).

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng gồm hai số nguyên p và q, cách nhau một dấu cách, thể hiện phân số nhỏ thứ k là p/q.

Ràng buộc

  • 1≤T≤5000
  • 1≤n≤109
  • 1≤k≤1018

Ví dụ

Input Output Giải thích
1
3 3
2 3 Với n=3, ba phần tử đầu tiên của dãy vô hạn là 1/3, 1/2 và 2/3.
4
1 5
4 4
4 6
2 3
5 1
2 4
3 4
2 2
Với n=4, dãy bắt đầu bằng 1/4,1/3,1/2,2/4,2/3,3/4,1/1,2/2,…; 1/2 và 2/4 cùng giá trị nên 1/2 (tử số nhỏ hơn) đứng trước. Với n=2, dãy bắt đầu bằng 1/2,1/1,2/2,…

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0