ShubhamRajput's blog

By ShubhamRajput, history, 7 years ago, In English

problem: http://www.spoj.com/problems/FINFRAC/ for q=1 , we can find integer x such that a/b < x and c/d > x ....then ans is x/1 but if the fractions a/b and c/d do not differ by 1 then I am unable to find out answer for minimum q ,even if I use binary search that will lead in TLE( by considering some q and find appropriate p).So it has to be mathematical.Also I know that (a+c)/(b+d) will be some fraction there and I can proceed to right half so that to find fraction between (a+2*c)/(b+2*d) and so on till I find lowest q (because we can reduce the fraction from gcd).Is there any better approach?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it