def gcd2(m, n):
    factor = 1

    while m > 1 and n > 1:

        if m % 2 == 0 and n % 2 == 0:
            factor *= 2
            m /= 2
            n /= 2
            continue
        elif m % 2 != 0 and n % 2 != 0:
            m, n = abs(m - n) / 2, min(m, n)
            continue

        if m % 2 == 0:
            m /= 2

        if n % 2 == 0:
            n /= 2

    if m == 0 or n == 0:
        out = m + n
    elif n == m:
        out = n
    elif m == 1 or n == 1:
        out = 1

    return factor * out


def gcd(m, n):
    if m == 0:
        return n

    if n == 0:
        return m

    if m == n:
        return n

    if m == 1 or n == 1:
        return 1

    if m % 2 == 0 and n % 2 == 0:
        return 2 * gcd(m / 2, n / 2)

    if m % 2 == 0 and n % 2 != 0:
        return gcd(m / 2, n)

    if n % 2 == 0 and m % 2 != 0:
        return gcd(m, n / 2)

    if m % 2 != 0 and n % 2 != 0:
        if n > m:
            return gcd((n-m)/2, m)

        else:
            return gcd((m-n)/2, n)

import random
import timeit

for test in range(100):
    a, b = random.randint(0, 100), random.randint(0, 100)
    fa = gcd(a, b)
    fb = gcd2(a, b)
    assert fa == fb, 'Not ok'

# number = 10 ** 5
# print timeit.timeit('gcd(a, b)', setup=s, number=number)
# print timeit.timeit('gcd2(a, b)', setup=s, number=number)
print 'ok'