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.
defegcd(a,b):ifa==0:return(b,0,1)else:g,y,x=egcd(b%a,a)return(g,x-(b// a) * y, y)defmodinv(a,m):g,x,y=egcd(a,m)ifg!=1:raiseException('modularinversedoesnotexist')else:returnx%mt=int(input())foriinrange(t):a,b,n=[int(x)forxininput().split()]inv_a=modinv(a,b)r=n%bd=r-inv_aifd<0:d+=bden=n-dnum=(den*a-1)// bprint("{}{}".format(num, den))
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 →
Here is my solution. Super fast in python 3