We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
thank for Kitchent's edit 2 : I used Extended Euclidean Algorithm (you can find it in internet) !
with input is "a" and "b" and "limit", and output "p" and "q";
the first you need find p/q < a/b : and condition is q < = limit; Because
Farey "neighbours" properties satisfied a*q-b*p=1 (1) or a*q=1+p*b because p*b=0 mod b therefor-> a*q=1 mod b , you use
Extended Euclidean Algorithm for this equation , you will find Q ,, --->
q= b* t + Q (2) , with "t =0,1,2,3,4,....." you to replace (2) in (1) -->
a*(b*t+Q)-1=p*b --> p=a*t + (a*Q-1)/b =a*t+ P with P= (a*Q-1)/b;
--> p/q=(a*t+ P)/( b* t + Q) with t=0,1,2,3,4....
because constion q < = limit --> b*t+Q < = limit -->t < = (limit-Q)/b ;
because t is natural number t == [ limit - Q / b ] you will find result in O(logb) ,
finally printf "p" and "q" //
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #71: Ordered fractions
You are viewing a single comment's thread. Return to all comments →
thank for Kitchent's edit 2 : I used Extended Euclidean Algorithm (you can find it in internet) ! with input is "a" and "b" and "limit", and output "p" and "q"; the first you need find p/q < a/b : and condition is q < = limit; Because Farey "neighbours" properties satisfied a*q-b*p=1 (1) or a*q=1+p*b because p*b=0 mod b therefor-> a*q=1 mod b , you use Extended Euclidean Algorithm for this equation , you will find Q ,, ---> q= b* t + Q (2) , with "t =0,1,2,3,4,....." you to replace (2) in (1) --> a*(b*t+Q)-1=p*b --> p=a*t + (a*Q-1)/b =a*t+ P with P= (a*Q-1)/b; --> p/q=(a*t+ P)/( b* t + Q) with t=0,1,2,3,4.... because constion q < = limit --> b*t+Q < = limit -->t < = (limit-Q)/b ; because t is natural number t == [ limit - Q / b ] you will find result in O(logb) , finally printf "p" and "q" //