How to solve N<10^6 or N<10^{15} versions of Neighbouring Fraction
For N < 10^2 I did simple brute search over all pairs (a,b). Ideas for higher constraint versions are welcome.
Use binary search
2 Likes
initially ln=0/1, rn=1/1
mid=0+1/1+1 = 1/2
check whether a/b lies to the left or right and repeat
A beautiful result is that if \frac{a}{b} is the neighbour of \frac{c}{d}, Then \frac{c}{d}-\frac{1}{bd}=\frac{a}{b}. So you can binary search on b.
2 Likes
oops didnt think of this
is the contest rated ?
One question got removed mid contest, Contest got stopped in the middle. I don’t see any reason for it to be unrated. 
I have an idea with this: let the final fraction be \frac{x}{y}, then ya-xb=1 and we can use the euclidean algorthm to get x=ak+x_0 and y=bk+y_0 in where we just take the largest y\leq n
this question is same as project euler 71
BTW congo fr 7 star 
We’ll not be moving it to Practice.
1 Like
OH! The tasks were copied thats why the contest was called off!