All Tracks Algorithms Searching Ternary Search Problem

( Problem C ) Pikachu and the floor problem
Tag(s):

Algorithms, Easy-Medium, Searching, Ternary Search

Problem
Editorial
Analytics

Team Rocket is back again and this time they have come with $$N$$ pokemon with strengths $$ 1,2,...N $$ .  They know that Pikachu has strength $$ P $$ and they are now training hard to fight against Pikachu.

Boss has given Team Rocket's pokemon special secret training number $$x$$ (a real number). This has increased the strength of all the Pokemon by a factor of $$x$$ , i.e. the new strengths of the $$ N  $$ pokemon are $$ x, 2x, .. , Nx $$ respectively. However pokemon do not like their strength being a real number and they have all rounded their strengths down to the greatest integer less than or equal to their strength.

After this special secret training, Team Rocket has claimed that the total sum of strengths of all the $$ N $$ pokemon has become exactly $$ P $$ and can beat Pikachu now. Pikachu doesn't like this and hence he wants to know the secret number $$ x $$ ( he knows the value of $$ N $$ and $$ P $$ ). Can you help Pikachu by telling him the value of $$ x $$ or tell that it is not possible to have any such $$ x $$? Since Pikachu doesn't like floating point numbers, he wants to know the greatest integer less than or equal to $$ x $$. You can assume that if there exist any such integer, then it is always unique.

Input Format :

The first line contains a single integer $$ t $$ denoting number of testcases in a single test file. Each testcase contains two integers $$N$$ and $$ p $$. 

Output Format :

Ouput a single integer denoting the output or $$ -1 $$ if there is no possible value of $$ x $$.

Input Constraints :

$$ 1 \le t \le 10^5 $$ 

$$ 1 \le  N \le  100000 $$

$$ 1 \le  p \le 10^{18} $$ 

The sum of $$N$$ over all tests is $$ \le 5 \times 10^5 $$ 

SAMPLE INPUT
5
5 1
5 10
5 19
5 20
5 21
SAMPLE OUTPUT
0
0
1
-1
1
Explanation

1. $$ x $$ can be $$ 0.2 $$ , because $$ [0.2] + [2*0.2] + [3*0.2] + [4*0.2] + [5*0.2] = 0 + 0 + 0 + 0 + 1 = 1  [0.2] = 0 $$

2. $$ x $$ can be $$ 0.8 $$, because $$ [0.8] + [2*0.8] + [3*0.8] + [4*0.8] + [5*0.8] = 0 + 1 + 2 + 3 + 4 = 10. [0.2] = 0 $$

3. $$ x  $$ can be $$ 1.4 $$, because $$ [1.4] + [2*1.4] + [3*1.4] + [4*1.4] + [5*1.4] = 1 + 2 + 4 + 5 + 7 = 19. [1.4] = 1 $$

4. You can prove that there exists no $$ x $$ such that $$ [x] + [2x] + [3x] + [4x] + [5x] = 20 $$.

5. $$ x $$ can be $$ 1.4 $$, because $$ [1.5] + [2*1.5] + [3*1.5] + [4*1.5] + [5*1.5] = 1 + 3 + 4 + 6 + 7 = 21. [1.5] = 1 $$

Here, $$ [z] $$ denotes the greatest integer less than or equal to the real number $$ z $$. 

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?