findFirstHitFast

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a,b%a; m,n = x-u*q,y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

precision = 1 << 20
def findFirstHitFast(a, b, c, d):
    a = long(a * precision)
    b = long(b * precision)
    c = long(c * precision)
    d = long(d * precision)
    m = gcd(b, c)
    k = (c-a) / m + 1
    s = b / m
    t = c / m
    inverse_s = modinv(s, t)
    n = k * inverse_s % t if inverse_s else precision
    print a, b, c, d, m, k, s, t, inverse_s, n
    return n