Problem:


最大公約数-ユークリッドの互除法

 最大公約数は、コンピュータ上で扱う数学には欠かせない要素です。最大公約 数を使うことで、計算の効率が大きく変動することもあります。最大公約数を求めるアルゴリズムのひとつが「ユークリッドの互除法」です。その処理 の流れを以下に示します。

例えば 1071 と 1029 の場合、1071 を X 、1029 を Y に代入して、

         1071 &divide; 1029 の余りは 42 、X に 42 を代入して X  と Y を入れ替える。 (1 ステップ)

           1029 &divide;   42 の余りは 21 、X  に 21 を代入して X と Y を入れ替える。 (2 ステップ)

                                                  
             42 &divide;   21 の余りは  0 、X に  0 を代入して X と Y を入れ替える。 (3 ステップ)

Y が 0 になったので、この時の X が最大公約数となる。よって最大公約数は 21 。

  このように、たったの 3 ステップで 1071 と 1029 の最大公約数を求めることが出来ました。ユークリッドの互除法は約数を出して比較していく方法に比べ、圧倒的に早く結果を出してくれます。

２つの整数を入力とし、ユークリッドの互除法を用いて最大公約数を求め、その最大公約数と計算にかかったステップ数を出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。
各データセットとして２つの整数 a, b (2 ≤ a, b ≤ 231-1) が１行に与えられます。

データセットの数は 1000 を超えません。

Output

データセットごとに、入力された２つの整数の最大公約数と、計算にかかったユークリッドの互除法のステップ数を空白区切りで１行に出力します。

Sample Input

1071 1029
5 5
0 0

Output for the Sample Input

21 3
5 1



Sample input:
1071 1029
5 5
0 0


Sample output:
21 3
5 1

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    c=0
    while b:(a,b),c=(b,a%b),c+1
    print(a,c)
while 1:
    n,m=map(int,input().split())
    if n==0:break
    gcd(n,m)

Submission status: Wrong Answer

Solution code:
# Aizu Problem 0197: Greatest Common Divisor: Euclidean Algorithm
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def extended_gcd(a, b):
    steps = 0
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a
    while r != 0:
        steps += 1
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, steps


while True:
    a, b = [int(_) for _ in input().split()]
    if a == b == 0:
        break
    g, steps = extended_gcd(a, b)
    print(g, steps)

Submission status: Wrong Answer

Solution code:
def gcd(a,b,i):
	return (a,i) if b == 0 else gcd(b,a%b,i+1)
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	g,i = gcd(n,m,0)
	print g,i

Submission status: Accepted

Solution code:
def euclidean_algorithm(x, y):
    cnt = 0

    if x < y:
        x, y = y, x
    while y:
        x = x % y
        x, y = y, x
        cnt += 1
    return x, cnt

import sys
f = sys.stdin

while True:
    a, b = map(int, f.readline().split())
    if a == 0:
        break
    print(*euclidean_algorithm(a, b))

Submission status: Accepted

Solution code:
while True:
    x, y = map(int, raw_input().split())
    if x == y == 0: break
    x, y = (x, y) if x >= y else (y, x)
    c = 0
    while y != 0:
        x = x-(x/y)*y
        x, y = y, x
        c += 1
    else:
        print x, c

Submission status: Accepted

Solution code:
def gcd(a,b):
    c=0
    while b:(a,b),c=(b,a%b),c+1
    print(a,c)
 
while 1:
    n,m=map(int,input().split())
    if n==0:break
    gcd(n,m) if n>m else gcd(m,n)

Submission status: Accepted

Solution code:
while True:
    x, y= map(int, input().split())
    if x==y==0: break
    if x< y: x, y= y, x
    step= 0
    while y> 0:
        x, y, step= y, x%y, step+1
    print(x, step)

Submission status: Accepted

Solution code:
# Aizu Problem 0197: Greatest Common Divisor: Euclidean Algorithm
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def extended_gcd(a, b):
    if a < b:
        a, b = b, a
    steps = 0
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a
    while r != 0:
        steps += 1
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t
    return old_r, steps


while True:
    a, b = [int(_) for _ in input().split()]
    if a == b == 0:
        break
    g, steps = extended_gcd(a, b)
    print(g, steps)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0197

"""
import sys
from sys import stdin
input = stdin.readline


def solve(a, b):
    count = 0
    if a > b:
        X, Y = a, b
    else:
        X, Y = b, a

    r  = 1
    while r:
        r = X % Y
        X = r
        X, Y = Y, X
        count += 1
    return X, count


def main(args):
    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break
        gcd, count = solve(a, b)
        print(gcd, count)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
while True:

    x, y = [int(item) for item in input().split(" ")]

    if x == 0:
        break

    if x < y:
        x, y = y, x

    count = 0

    while y != 0:
        x = x % y
        x, y = y, x
        count += 1

    print(x, count)

Submission status: Accepted

Solution code:
def euclid_gcd(v1, v2, counter):
  if v2 == 0:
    return (v1, counter)
  else:
    return euclid_gcd(v2, v1 % v2, counter + 1)

while True:
  a, b = map(int, input().split())
  if a == 0:
    break

  a, b = max(a, b), min(a, b)
  print(*euclid_gcd(a, b, 0))

Submission status: Accepted

Solution code:
# AOJ 0197 Greatest Common Divisor
# Python3 2018.6.18 bal4u

def gcd(a, b):
	k = 0
	while b != 0:
		r = a % b
		a, b = b, r
		k += 1
	return [a, k]

while True:
	x, y = list(map(int, input().split()))
	if x == 0: break
	if x < y: x, y = y, x
	ans = gcd(x, y)
	print(*ans)

Submission status: Accepted

Solution code:
def ans(x,y,z):
  z+=1
  x = x%y
  x,y = y,x
  if y == 0:return x,z
  return ans(x,y,z)
while True:
  a,b = map(int,raw_input().split())
  if a+b == 0: break
  if b > a: a,b =b,a
  d=0
  c,e =ans(a,b,d)
  print c,e

Submission status: Accepted

Solution code:
def gcd(a,b):
    c = 0
    if a < b:
        a,b = b,a
    while b!=0:
        a,b = b,a%b
        c += 1
    return a,c
while True:
    n,m = map(int,raw_input().split())
    if (n,m) == (0,0):
        break
    print "{} {}".format(*gcd(n,m))

Submission status: Accepted

Solution code:
while 1:
    m,n = map(int, raw_input().split())
    if m==n==0: break
    if m<n: m,n = n,m
    r = 1; c = 0;
    while 1:
        c += 1; r = m%n;
        if r==0: break
        n,m = r,n;
    print n, c

Submission status: Accepted

Solution code:
def gcd(a,b,i):
	return (a,i) if b == 0 else gcd(b,a%b,i+1)
while 1:
	n,m = sorted(map(int,raw_input().split()),reverse = True)
	if n == m == 0: break
	g,i = gcd(n,m,0)
	print g,i

Submission status: Accepted

Solution code:
while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    
    ans=0
    while True:
        if y==0:
            break
        if x<y:
            x,y=y,x
        x=x%y
        x,y=y,x
        ans+=1
    
    print(x,ans)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())

    if a==0:
        break
    else :
        if a<=b:
                X,Y = b,a
        else :
            X,Y = a,b
            
        s=0
                
        def c(X, Y, s) :
            while Y != 0 :
                s += 1
                X %= Y
                X, Y = Y, X
                
            return X, s
            
        print(c(X, Y, s)[0], c(X, Y, s)[1])

Submission status: Accepted

Solution code:
while True:
    x,y=map(int,input().split())
    if x<=y:
        x,y=y,x
    if x==y==0:
        break
    z=0
    while True:
        if y==0:
            break
        x=x%y
        x,y=y,x
        z+=1
    print(x,z)

Submission status: Accepted

Solution code:
def gcd(a,b):
    c = 0
    while b:
        (a,b),c = (b,a%b),c+1
    print(a,c)
        
while True:
    N,M = map(int,input().split())
    if N == 0:
        break
    gcd(N,M) if N>M else gcd(M,N)

Submission status: Accepted

Solution code:
while True:
    try:
        m = list(map(int,input().split()))
        if m[0] == 0 and m[1] == 0:
            break
    except EOFError:
        break

    m.sort(reverse=True)
    x = m[0]
    y = m[1]
    a = 0
    while y != 0:
        a += 1
        x = x % y
        x,y = y,x

    print(x,a)

Submission status: Accepted

Solution code:
def gcd(a,b):
    c=0
    while b:(a,b),c=(b,a%b),c+1
    print(a,c)
  
while True:
    n,m=map(int,input().split())
    if n==0:break
    gcd(n,m) if n>m else gcd(m,n)

Submission status: Accepted

Solution code:
def gcd(a, b):
	k = 0
	while b != 0:
		r = a % b
		a, b = b, r
		k += 1
	return [a, k]

while True:
	x, y = list(map(int, input().split()))
	if x == 0: break
	if x < y: x, y = y, x
	ans = gcd(x, y)
	print(*ans)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    if a>=b:
        X=a
        Y=b
    else:
        X=b
        Y=a
    C=0    
    while Y!=0:
        X=X%Y  
        X,Y=Y,X
        C+=1
    else:
        print(X,C)

Submission status: Accepted

Solution code:
while True:
    x,y = map(int, input().split())
    if x ==0 and y ==0 :
        break
    
    ans=0
    while True:
        if y == 0:
            break
        if x < y:
            x,y= y,x
        x= x%y
        x,y = y,x
        ans+=1   
    print(x, ans)

Submission status: Accepted

Solution code:
while True:
    x,y = map(int,input().split())
    if x==0 and y==0: break

    a = max(x,y)
    b = min(x,y)
    p = 0
    while True:
        p += 1
        q = a%b
        a,b = b,q
        if q==0: break
    print(a,p)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    c=0
    if a<b:
        a,b=b,a
    while b!=0:
        c+=1
        d=a%b
        a=b
        b=d
    print(a,c)

Submission status: Accepted

Solution code:
while True:
    c=0
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    if n<m:
        n,m=m,n
    while True:
        if m==0:
            print(n,c)
            break
        n=n%m
        n,m=m,n
        c=c+1

Submission status: Accepted

Solution code:
while True:
    m,n=map(int,input().split())
    if m==n==0:
        break
    b=0
    if m<n:
        m,n=n,m
    while n!=0:    
        a=m%n
        m=n
        n=a
        b+=1
    print(m,b)

Submission status: Accepted

Solution code:
while True:
    try:
        a,b=map(int,input().split())
        if a==0 and b==0:
            break
        else:
            if a<b:
                a,b=b,a
            else:
                pass
            i=0
            while True:
                c=a%b
                a=b
                b=c
                i+=1
                if b==0:
                    break
            print(a,i)
    except EOFError:
        pass

Submission status: Accepted

Solution code:
while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    count=0
    if y>x:
        x,y=y,x
    while y!=0:
        x=x%y
        x,y=y,x
        count+=1
    print(x,count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

while True:
   a, b = map(int, input().split())
   if a + b == 0:
      break
   
   c = 0
   if a < b:
      a, b = b, a
   while b != 0:
      c += 1
      r = a % b
      a = b
      b = r
   print(a, c)

Submission status: Accepted

Solution code:
while True:
    a,b = [int(i) for i in input().split()]

    if a == 0 and b == 0:
        break

    if a < b:
        a,b = b,a

    c = 0
    while b > 0:
        a, b = b, a % b
        c += 1

    print(a, c)

Submission status: Accepted

Solution code:
def gcd(a,b):
    c=0
    while b:(a,b),c=(b,a%b),c+1
    print(a,c)
  
while 1:
    m,n=map(int,input().split())
    if m==0:break
    gcd(m,n) if m>n else gcd(n,m)

Submission status: Accepted

Solution code:
while True:
  a,b = map(int,input().split())
  if (a,b) == (0,0):
    break
  x = max(a,b)
  y = min(a,b)
  c = 0
  while y != 0:
    x %= y
    x,y = y,x
    c += 1
  print(x,c)

Submission status: Accepted

Solution code:
while True:
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    
    X=max(n,m)
    Y=min(n,m)
    
    a=0
    while True:
        a+=1
        tmp=X%Y
        X,Y=Y,tmp
        if tmp==0:
            break
        
    print(X,a)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
while True:
    X,Y=map(int, input().split())
    if X==Y==0:
        break
    
    i=0
    if X<Y:
        X,Y=Y,X
    
    while Y!=0:
        X=X%Y
        X,Y=Y,X
        i+=1
    
    print(X, i)

Submission status: Accepted

Solution code:
def gcd(a, b):
	k = 0
	while b != 0:
		r = a % b
		a, b = b, r
		k += 1
	return [a, k]

while True:
	x, y = list(map(int, input().split()))
	if x == 0: break
	if x < y: x, y = y, x
	ans = gcd(x, y)
	print(*ans)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    if a<b:
        a,b=b,a
    C=0
    while True:
        a=a%b
        a,b=b,a
        C=C+1
        if b==0:
            break
    print(a,C)

Submission status: Accepted

Solution code:

import datetime

while 1:
    c = 0
    a,b = map(int,input().split())
    if a == 0:
        break

    if b > a:
        a,b = b,a

    while b != 0:
        a = a % b
        a, b = b, a
        c += 1
    print(a,c)

Submission status: Accepted

Solution code:
while True:
    l = []
#    x , y = reversed(list(map(int, input().split())))
    x , y = map(int, input().split())
    if (x,y) == (0,0):
        break
    #print(x,y,"*")

    if x<=y :
        def gcd(y, x):
            if x == 0:
                #print(l,x,y,"$")
                return y
            else:
                l.append(1)
                #print(l,x,y)
                return gcd(x, y % x) #再帰
        print(gcd(y,x),end="")
        print("",sum(l))
    elif x == y :
        print(x,1)

    else:
        def gcd(x, y):
            if y == 0:
                #print(l,x,y,"*")
                return x

            else:
                l.append(1)
                #print(l,x,y)
                return gcd(y, x % y) #再帰

        print(gcd(x,y),end="")
        print("",sum(l))

Submission status: Accepted

Solution code:
# 75
while True:
    X,Y = (int(x) for x in input().split())
    if X == 0 and Y == 0:
        break
    elif X < Y:
        X,Y = Y,X

    i = 0
    while Y != 0:
        X = X % Y
        X,Y = Y,X
        i += 1

    print(X, i)

Submission status: Accepted

Solution code:
while True:
    x,y = map(int,input().split())
    if x == 0 and y == 0:
        break
    if x < y:
        x,y=y,x
    c = 0
    while True:
        if y == 0:
            break
        x = x % y
        x,y=y,x
        c += 1
    print(x,c)

Submission status: Accepted

Solution code:
while True:
    X,Y=map(int,input().split())
    if X==0 and Y==0:
        break
    n=0
    while True:
        if Y==0:
            break
        elif X<=Y:
            X,Y=Y,X
        X%=Y
        X,Y=Y,X
        n+=1
    print(X,n)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==0 and b==0 :
        break
    if a<b: (a,b)=(b,a)
    k=1
    while True :
        B=a%b
        if B==0:
            break
        k+=1
        a=b
        b=B
    print(b,k)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

while True:
    a,b = [int(i) for i in input().split()]
    if a == 0 and b == 0:
        break
    
    if a < b:
        a, b = b, a
    
    c = 0
    while b > 0:
        a, b = b, a % b
        c += 1
    
    print(a, c)

Submission status: Accepted

Solution code:
#75 最大公約数-ユークリッドの互除法

while True :
    x, y = map(int, input().split())
    if x == y == 0:
        break
    if x < y: x, y = y, x
    step = 0
    while y > 0:
        x, y, step = y, x%y, step+1
    print(x, step)

Submission status: Accepted

Solution code:
while True:
    a,b = [int(i) for i in input().split()]

    if a == 0 and b == 0:
        break

    if a < b:
        a,b = b,a

    cnt = 0
    while b > 0:
        a, b = b, a % b
        cnt += 1

    print(a, cnt)

Submission status: Accepted

Solution code:
for i in range(1000):
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    if y > x:
        x,y=y,x
    else:
        x,y=x,y


    count=0
    for i in range (1000):
        
        if y==0:
            break
        x=x%y
        x,y=y,x
        count+=1
        
        
    print("{} {}".format(x,count))

Submission status: Accepted

Solution code:
while True:
    y, x = sorted(map(int, input().split()))
    if x == y == 0:
        break
    cnt = 0
    while y != 0:
        x = x % y
        x, y = y, x
        cnt += 1
    print(x, cnt)

Submission status: Accepted

Solution code:
while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    num=0
    while True:
        num+=1
        if x==0:
            print(y,num-1)
            break
        elif y==0:
            print(x,num-1)
            break
        
        elif x>=y:
            x=x%y
        elif x<y:
            y=y%x

Submission status: Accepted

Solution code:
def gcd(a,b):
    k=0
    while b != 0:
        r=a%b
        a=r
        a,b=b,a
        k+=1
    return[a,k]
        
while True:
    m,n=map(int,input().split())
    if m==0:break
    if m<n:m,n=n,m
    ans = gcd(m, n) #print(math.gcd(a, b)) #二つの整数を渡すと最大公約数を返す    s=0
    print(*ans)

Submission status: Accepted

Solution code:
while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0: break

    x = max(a, b)
    y = min(a, b)

    count = 0
    while 1:
        count += 1
        z = x % y
        x, y = y, z
        if z == 0:
            break

    print(x, count)

Submission status: Accepted

Solution code:
while True:
    x, y = map(int, input().split())
    count = 0
    
    if x == 0 and y == 0:
        break
    if x < y:
        x, y = y, x

    while y > 0:
        x, y = y, x%y
        count += 1
    print(x, count)

Submission status: Accepted

Solution code:
while True :
    x, y = map(int, input().split())
    if x == 0 and y == 0 :
        break
    
    ans = 0
    while True :
        if y == 0 :
            break
        if x < y :
            x, y = y, x
        x = x % y
        x, y = y, x
        ans += 1
    
    print(x, ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
  k = 0
  while b != 0:
    r = a % b
    a, b = b, r
    k += 1
  return[a, k]
while True:
  x, y = list(map(int, input().split()))
  if x == 0: break
  if x < y:
    x, y = y, x
  ans = gcd(x, y)
  print(*ans)

Submission status: Accepted

Solution code:
while True:
    c=0
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    if n<m:
        n,m=m,n
    while True:
        if m==0:
            print(n,c)
            break
        n=n%m
        n,m=m,n
        c=c+1

Submission status: Accepted

Solution code:
while True:
    n,m = map(int,input().split())
    if n==0 and m==0:
        break
    step = 0
    if n >= m:
        X = n
        Y = m
        while True:
            X = X % Y
            X,Y = Y,X
            step +=1
            if Y == 0:
                ans = X
                break
    else:
        X = m
        Y = n
        while True:
            X = X % Y
            X,Y = Y,X
            step +=1
            if Y == 0 :
                ans = X
                break
    print(ans,step)

Submission status: Accepted

Solution code:
def Euclidean(a,b):
    if a>=b:
        x=a
        y=b
    else:
        x=b
        y=a
    n=0
    while y!=0:
        x=x%y
        x,y=y,x
        n+=1
    print(x,n)

while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    Euclidean(a,b)

Submission status: Accepted

Solution code:
while True:
    a, b = map(int, input().split())
    if a==0 and b==0:
        break
    if a < b:
        a, b = b, a
    x=1
    while a % b != 0:
        a, b = b, a % b
        x+=1
    print(b,x)

Submission status: Accepted

Solution code:
while 1:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break

    x = max(a, b)
    y = min(a, b)

    cnt = 0
    while 1:
        cnt += 1
        tmp = x % y
        x, y = y, tmp
        if tmp == 0:
            break

    print(x, cnt)

Submission status: Accepted

Solution code:
while True:
    a,b = map(int,input().split())
    count = 0
    if a == 0 and b == 0:
        break
    elif a < b:
        a,b = b,a
        
    while True:
        if b == 0:
            break
        a = a % b
        a,b = b,a
        count += 1
    print(a,count)

Submission status: Accepted

Solution code:
while True:
   x,y = map(int, input().split())
   if x==0 and y==0:
      break
   elif x<y:
      X=y
      Y=x
   else:
      X=x
      Y=y
   i = 0
   while True:
      a = X%Y
      X = a
      Z = Y
      Y = X
      X = Z
      i += 1
      if a==0:
         break
   print(X, i)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==b==0:
        break
    else:
        if a>=b:
            x=a
            y=b
        else:
            x=b
            y=a
        
        s=0
        while True:
            x=x%y
            x,y=y,x
            
            s+=1
            if y==0:
                break
        print(x,s)

Submission status: Accepted

Solution code:
c=0
while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    
    if x<y:
        x,y=y,x
    
    while True:
        if y==0:
            break
        
        x=x%y
        x,y=y,x
        c+=1
        
    print(x,c)
    c=0

Submission status: Accepted

Solution code:
def gcd(a,b):
    i=0
    while b!=0:
        c=a%b
        a,b=b,c
        i+=1
    return [a,i]
            
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    if a<b:
        a,b=b,a
    print(*gcd(a,b))

Submission status: Accepted

Solution code:
def gozyo(x,y):
    w = 0
    while True:
        if y == 0:
            return x,w
        x = x % y
        z = x
        x = y
        y = z
        w += 1
    

while True:
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        break
    if a < b:
        c = a
        a = b
        b = c
    u = gozyo(a,b)
    print(u[0],u[1])

Submission status: Accepted

Solution code:
while True:
    a, b = map(int,input().split())
    if a==0 and b==0:
        break
    if a <= b:
        a, b = b, a
    d = 1
    while True:
        c = a%b
        if c==0:
            break
        if c!=0:
            a,b = b, c
            d += 1
    print(b,d)

Submission status: Accepted

Solution code:
while True:
    a, b = map(int,input().split())
    if a == 0 and b == 0:
        break
    if a < b:
        a, b = b, a
    C = 0
    while True:
        C  = C + 1
        a = a % b
        if a == 0:
            break
        a, b = b, a
    print(b, C)

Submission status: Accepted

Solution code:
while True:
    a,b = map(int,input().split())
    if a==0 and b==0:
        break
    if a<b:
        a,b = b,a
    p=0
    while b != 0:
        c = a % b
        a,b = b,c
        p += 1
    print(a,p)

Submission status: Accepted

Solution code:
while True:
    n,m=map(int,input().split())
    if n==0 and m==0:
        break
    else:
        if n>=m:
            x,y=n,m
        else:
            x,y=m,n
        s=0
        while True:
            if y!=0:
                x=x%y
                x,y=y,x
                s+=1
            else:
                break
    print(x,s)

Submission status: Accepted

Solution code:
while True:
    a, b = map(int,input().split())
    X = 0
    Y = 0
    n = 0
    
    if a == 0 and b == 0:
        break

    if a >= b:
        X = a
        Y = b
    else:
        X = b
        Y = a

    while Y != 0:
        X,Y = Y,X%Y
        n += 1
    
    print(X,n)

Submission status: Accepted

Solution code:
while True:
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        break
    X = max(a,b)
    Y = min(a,b)
    
    count = 0
    while True:
        count += 1
        d = X % Y
        X,Y = Y,d
        if d == 0:
            break
    print(X,count)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    
    if a<b:
        a,b=b,a
        
    sum=0
    while b>0:
        a=a%b
        a,b=b,a
        sum+=1
        
    print(a,sum)

Submission status: Accepted

Solution code:
while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break
    if a < b:
        a, b = b, a
        
    X = a
    Y = b
    i = 0
    
    while True:
        X %= Y
        X, Y = Y, X
        i += 1
        if Y == 0:
            break
            
    print(X,i)

Submission status: Accepted

Solution code:
while True:
    x,y=map(int,input().split())
    if x<y:
        x,y=y,x
    count=0
    if x==0 and y==0:
        break
    while y!=0:
        a=x%y
        x=a
        x,y=y,x
        count+=1
    print(x,count)

Submission status: Accepted

Solution code:
while True:
    x,y=map(int, input().split())
    if x==y==0:
        break
    
    i=0
    if x<y:
        x,y=y,x
    
    while y!=0:
        x=x%y
        x,y=y,x
        i+=1
    
    print(x, i)

Submission status: Accepted

Solution code:
# coding: utf-8
# 75
k=0

while True:
    x,y = map(int,input().split())
    if x==0 and y==0:
        break
    if y>x:
        x,y=y,x
    while y>0:
        r = x
        x = y
        y = r%y
        k += 1
  
    print(x,k)
    k=0

Submission status: Accepted

Solution code:
#0197
while True:
    c = 0
    a = 0
    b = 0
    x , y = map(int,input().split())
    if x == y == 0:
        break
    if x < y:
        a = x
        x = y
        y = a
    
    while True:
        b = x%y
        x = y
        y = b
        c += 1
        if y == 0:
            break
    print(x,c)

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==0 or b==0: break
    if a<b: a,b=b,a
    p=0
    while b != 0:
        c=a%b
        a,b=b,c
        p+=1
    print(a,p)

Submission status: Accepted

Solution code:
while 1:
    x, y = map(int,input().split())
    if x == 0 and y == 0:
        break
    
    if x < y:
        (x, y) = (y, x)
   
    i = 0
    while 1:
        if y == 0:
            print(x, i)
            break
        i += 1
        z = x % y
        x = z
        (x, y) = (y, x)

Submission status: Accepted

Solution code:
while True:
    try:
        a,b=map(int,input().split())
        if a==0 and b==0:
            break
        else:
            if a<b:
                a,b=b,a
            else:
                pass
            i=0
            while True:
                c=a%b
                a=b
                b=c
                i+=1
                if b==0:
                    break
            print(a,i)
    except EOFError:
        pass

Submission status: Accepted

Solution code:
while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    else:
        if x<y:
            x,y=y,x
        i=0
        while True:
            if y==0:
                break
            else:
                i+=1
                d=x%y
                x=d
                x,y=y,x
    print(x,i)

Submission status: Accepted

Solution code:
import sys
def f(d,x,y):
    t = x % y
    x = y
    y = t
    if y != 0:
        return f(d+1,x,y)
    else:
        return (x,d+1)

while 1:
    y,x = sorted(list(map(int, input().split())))
    if x == 0: break
    ans = f(0,x,y)
    print(ans[0],ans[1])

Submission status: Accepted

Solution code:

while True:
    x,y = map(int,input().split())
    if x==y==0: break
    cnt = 0
    x,y = max(x,y),min(x,y)
    
    while y!=0:
        x,y = y,x%y; cnt += 1

    print(x,cnt)

Submission status: Accepted

Solution code:
while True:
    X,Y=map(int,input().split())
    if (X,Y)==(0,0):
        break
    if X>=Y:
        pass
    else:
        t=Y
        Y=X
        X=t
    c=0
    while True:
        if Y==0:
            break
        X%=Y
        t=X
        X=Y
        Y=t
        c+=1
    print(X,c)

Submission status: Accepted

Solution code:
#入力が2つ0なら処理を終わる
while True:
    a,b = map(int,input().split())
    if a == 0 and b == 0:break

    #2つの数の中で大きい方をa小さい方をbに入れる
    a,b = max(a,b),min(a,b)
    
    #カウンタ変数の初期化
    i = 0
    
    #bが0になったらユークリッドの互除法を終わる
    while True:
        
        #カウンタ変数の更新
        i += 1
        
        #a/bのあまりをaに代入、aとbの値を交換する
        a = a % b
        a,b = b,a
        if b == 0:break
    
    #公約数と回数を出力する
    print(a,i)

Submission status: Accepted

Solution code:
while True:
    x,y = map(int,input().split())
    
    if x==0 and y==0:
        break
    
    
    if x < y:
        x,y = y,x
    
    z = 0
    while True:
        z += 1
        tmp = x % y
        x, y = y, tmp
        if tmp == 0:
            break

    print(x, z)

Submission status: Accepted

Solution code:
while True:
    count=0
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    elif a<b:
        a,b=b,a
    while True:
        if b==0:
            break
        a=a%b
        a,b=b,a
        count+=1
    print(a,count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

while True:
   a, b = map(int, input().split())
   if a + b == 0:
      break
   
   c = 0
   if a < b:
      a, b = b, a
   while b != 0:
      c += 1
      r = a % b
      a = b
      b = r
   print(a, c)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    ans = ""
    
    while True:
        a, b = map(int, f_i.readline().split())
        
        if a == 0 and b == 0:
            break
        
        if a < b:
            a, b = b, a
        
        # Euclidean Algorithm
        cnt = 1
        while a % b != 0:
            cnt += 1
            a, b = b, a % b
        
        ans += f"{b} {cnt}\n"
    
    print(ans, end='')

solve()

Submission status: Accepted

Solution code:
while True:
    x, y = map(int, input().split())
    
    if x==0 and y==0:
        break
    
    if x<y:
        x, y = y, x
    
    count = 0
    while y>0:
        x = x%y
        x, y = y, x
        count += 1
    
    print(x,count)

Submission status: Accepted

Solution code:
while True :
    x, y = map(int, input().split())
    if x == 0 and y == 0 :
        break
    
    ans = 0
    while True :
        if y == 0 :
            break
        if x < y :
            x, y = y, x
        x = x % y
        x, y = y, x
        ans += 1
    
    print(x, ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    c = 0
    while b != 0:
        a,b = b,a % b
        c += 1
    return [a,c]
    
while 1:
    x,y = map(int,input().split())
    if x == 0:
        break
    
    x,y = max(x,y),min(x,y)
    print(*(gcd(x,y)))

Submission status: Accepted

Solution code:
while True :
    a, b = map(int, input().split())

    if a == 0 :
        break
    else :
        if a <= b :
                X, Y = b, a
        else :
            X, Y = a, b
            
        cnt = 0
                
        def Euc(X, Y, cnt) :
            while Y != 0 :
                cnt += 1
                X %= Y
                X, Y = Y, X
                
            return X, cnt
            
        print(Euc(X, Y, cnt)[0], Euc(X, Y, cnt)[1])

Submission status: Accepted

Solution code:
while True:
    x, y = [int(x) for x in input().split()]
    if x == 0 and y == 0:
        break
    
    c = 0
    if y > x:
        x,y = y, x
    while True:
        c += 1
        x = x % y
        x,y = y,x
        if y == 0:
            break
    
    print(x,c)

Submission status: Accepted

Solution code:
def gcd(a,b):
    c=0
    while b:(a,b),c=(b,a%b),c+1
    print(a,c)
  
while 1:
    n,m=map(int,input().split())
    if n==0:break
    gcd(n,m) if n>m else gcd(m,n)