Remainder Twist
Practice
4.8 (4 votes)
Algorithms
Binary search
Problem
72% Success 1372 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code
Alice is in love with remainders. His friend Bob gifted her the number \(R\).
A function \(F(X)\) is defined as the number of possible pairs \((A,B)\) such that the following conditions are satisfied:
- \(A\) and \(B\) are positive integers less than or equal to \(N\).
- \(A\%B\), the remainder when \(A\) is divided by \(B\), is greater than or equal to \(X\).
Find the maximum possible non-negative integer \(Y\), such that \(F(Y)\) is greater than or equal to \(R\). If it is impossible to find such an integer, print \(-1\).
Input Format
- The first line contains an integer \(T\), which denotes the number of test cases.
- The first line of each test case contains two integers, \(N\) and \(R\).
Output Format
For each test case, print \(Y\), the maximum possible non-negative integer such that \(F(Y)\) is greater than or equal to \(R\). If it is impossible to find such an integer, return \(-1\).
Constraints
\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq R \leq 10^9\)
Submissions
Please login to view your submissions
Similar Problems
Points:50
6 votes
Tags:
Binary SearchAlgorithmsGreedy Algorithms
Points:50
36 votes
Tags:
AlgorithmsApprovedBinary SearchHardOpenSorting
Points:50
7 votes
Tags:
Binary SearchAlgorithmsC++
Editorial