Pro.ID21675 TitleFarey Sequence Again Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21675 AC0 Submit0 Ratio- 时间&空间限制描述The Farey sequence Fn for any positive integer n is the set of irreducible rational numbers a/b with 0 < a < b ≤ n and (a, b) = 1 arranged in increasing order. Here (a, b) mean the greatest common divisor of a and b. For example: F2 = {1/2} F3 = {1/3, 1/2, 2/3} Given two positive integers N and K, with K less than N, you need to find out the K-th smallest element of the Farey sequence FN. 输入The first line of input is the number of test case T, 1 ≤ T ≤ 1000. Then each test case contains two positive integers N and K. 1 ≤ K < N ≤ 109. 输出Description The Farey sequence Fn for any positive integer n is the set of irreducible rational numbers a/b with 0 < a < b ≤ n and (a, b) = 1 arranged in increasing order. Here (a, b) mean the greatest common divisor of a and b. For example: F2 = {1/2} F3 = {1/3, 1/2, 2/3} Given two positive integers N and K, with K less than N, you need to find out the K-th smallest element of the Farey sequence FN. Input The first line of input is the number of test case T, 1 ≤ T ≤ 1000. Then each test case contains two positive integers N and K. 1 ≤ K < N ≤ 109. Output For each test case output the K-th smallest element of the Farey sequence FN in a single line. Sample Input 3 Sample Output 1/2 Source 样例输入3 样例输出1/2 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 14:53 , Processed in 0.015550 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
