Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Justify the Invention !

By asifthegreat · Limits 1s, 256 MB

You probably heard of Professor Meiokoyi, a talented scientist. Recently she invented a new solution of Josephus problem.

Basically in the Josephus problem, We place nn people indexed from 11 to nn in a circle and eliminate every second remaining person until there's only one remaining. The last person is our winner. If you still wondering what it is, then check this.

Suppose the index of the last person is J(n)J(n). Now Professor Meiokoyi claims that J(n)J(n) will always be n2\displaystyle{\frac{n}{2}}. So she submitted her invention to Hakayaki Science federation. Now the federation has some rules. They won't mark the invention valid until it's properly checked. So they will randomly choose a number xx from a range L..RL..R . If J(x)=x2J(x) = \displaystyle{\frac{x}{2}}, they will mark the invention valid, otherwise not. Now you are given L,RL,R and you have to find the probability of getting her invention validated.


In the first line, you're given an integer QQ (1Q2×1051 \leq Q \leq 2 \times 10^5).

Each of the next QQ lines will have two numbers L,RL, R ( 1LR26311 \leq L \leq R \leq 2^{63}-1 ).


For Each Query, print the probability of getting her invention valid. Suppose your answer is xx and the judge answer is yy. Your answer will considered correct if and only if yx  108 \mid y-x \mid ~~ \leq 10^{-8}. Don't forget to print a newline after every answer.


5 10
20 40



83% Solution Ratio

EgorKulikovEarliest, Apr '20

skmonirFastest, 0.1s

vipghn2003Lightest, 2.2 MB

Dipto_DebdipShortest, 237B


Login to submit


If J(n)=n2J(n) = \displaystyle{\frac{n}{2}}J(n)=2n​ , binary representation of nnn will be 101010......

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.