Problem:


Score : 500 points

Problem Statement

Snuke is conducting an optical experiment using mirrors and his new invention, the rifle of Mysterious Light.

Three mirrors of length N are set so that they form an equilateral triangle.
Let the vertices of the triangle be a, b and c.

Inside the triangle, the rifle is placed at the point p on segment ab such that ap = X.
(The size of the rifle is negligible.)
Now, the rifle is about to fire a ray of Mysterious Light in the direction of bc.

The ray of Mysterious Light will travel in a straight line, and will be reflected by mirrors, in the same ways as "ordinary" light.
There is one major difference, though: it will be also reflected by its own trajectory as if it is a mirror!
When the ray comes back to the rifle, the ray will be absorbed.

The following image shows the ray's trajectory where N = 5 and X = 2.

It can be shown that the ray eventually comes back to the rifle and is absorbed, regardless of the values of N and X.
Find the total length of the ray's trajectory.

Constraints

2≦N≦10^{12}

1≦X≦N-1

N and X are integers.

Partial Points

300 points will be awarded for passing the test set satisfying N≦1000.

Another 200 points will be awarded for passing the test set without additional constraints.

Input

The input is given from Standard Input in the following format:

N X

Output

Print the total length of the ray's trajectory.

Sample Input 1

5 2

Sample Output 1

12

Refer to the image in the Problem Statement section.
The total length of the trajectory is 2+3+2+2+1+1+1 = 12.



Sample input:
5 2


Sample output:
12

Submission status: Accepted

Solution code:
N,X = map(int,input().split(" "))
 
Y,X = sorted([N - X,X])
 
s = 0
while Y:
    s += (X//Y)*Y*3
    Y,X = [X%Y,Y]
 
print(s)

Submission status: Accepted

Solution code:
def calc(a,b,ans):
  if b==0:
    return ans
  else:
    return calc(b,a%b,ans+b*(a//b)*3)

n,x=map(int,input().split())
n=n-x
n,x=max(n,x),min(n,x)
print(calc(n,x,0))

Submission status: Accepted

Solution code:
N,X = map(int,input().split(" "))

Y,X = sorted([N - X,X])

s = 0
while Y:
    s += (X//Y)*Y*3
    Y,X = [X%Y,Y]

print(s)

Submission status: Accepted

Solution code:
N,X = map(int, input().split())

if N/2 == X:
    l = X*3
elif N/2 > X:
    l = N
    x = X
    n = N - X
    while x > 0:
        l += (n//x)*2*x
        c = x
        x = n%x
        n = c
    l -= n
else:
    l = N
    x = X
    n = N - X
    while x > 0:
        l += (n//x)*2*x
        c = x
        x = n%x
        n = c
    l -= n
print(l)

Submission status: Accepted

Solution code:
n, x = [int(i) for i in input().split()]

cnt=0

short = min(x,n-x)
long  = max(x, n-x)
cnt += n
#cnt += x*(2*(n//x)-1) + (n-x)

while(1):
    c = long % short
    a = long //short
    if c==0:
        break
    else:
        cnt += short * 2 * a
        long = short
        short = c

cnt += short * (2 * a -1)
print(cnt)

Submission status: Accepted

Solution code:
def f(a,b):
	if a==b:
		d=0
		ret = a
	elif a < b:
		d = b//a
		if b%a == 0:
			ret = a*(2*d -1)
		else:
			ret = 2*a*d + f(a,b%a)
	else:
		d = a//b
		if a%b == 0:
			ret = b*(2*d -1)
		else:
			ret = 2*b*d + f(a%b,b)
	#print(a,b,d,ret)
	return ret


N,X = map(int,input().split(" "))

print(N+f(N-X,X))

Submission status: Accepted

Solution code:
"""B - Mysterious Light"""
N,X=(int(i) for i in input().split())
def MysteriousLight(tmp,rem):
    while rem:
        tmp, rem= rem,tmp%rem
    return tmp

print(3*(N-MysteriousLight(N,X)))

Submission status: Accepted

Solution code:
N, X = list(map(int, input().split()))
ans = N
a, b = sorted([X, N - X])
while True:
    if b % a == 0:
        ans += (int(b / a) * 2 - 1) * a
        break
    else:
        ans += int(b // a) * a * 2
        a, b = b % a, a

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def rli():
    return list(map(int, input().split()))


def solve(n, x):
    if x < n - x:
        x = n - x
    w = n - x
    t = (w - (x % w)) % w
    res = (x + w - 1) // w * 3 * w - t * 3
    if t != 0:
        res += solve(w, w - t)
    return res


def main():
    n, x = rli()
    print(solve(n, x))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
total = n
a = x
b = n - x
while a > 0:
    total += (a * 2) * (b // a)
    a, b = b % a, a
print(total - b)

Submission status: Accepted

Solution code:
N,x=map(int,input().split())
x=min(x,N-x)
rem=[N-x,x]
len=x
ans=N
i=1

while True:
  i=(i+1)%2
  ans+=2*(rem[i]//len)*len
  rem[i]=rem[i]%len
  if rem[i]!=0:
  	len=rem[i]
  else:
    break
  
print(ans-len)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
def f(a,b):
    if a>b:
        return f(b,a)
    if b%a==0:
        return a*(2*(b//a) - 1)
    return 2*(b//a)*a + f(b%a,a)
print(N+f(X,N-X))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x = na()

def loop(a,b):
    h = max(a,b)
    w = min(a,b)
    if h%w == 0:
        return int((2*h/w-1)*w)
    else:
        m = h%w
        q = h//w
        return 2*q*w + loop(m,w)

print(loop(x,n-x)+n)

Submission status: Accepted

Solution code:
def f(a,b):
    a,b=min(a,b),max(a,b)
    if b%a==0:
        return (2*b//a-1)*a
    else:
        return 2*a*(b//a)+f(a,b%a)

n,x=map(int,input().split())
print(n+f(x,n-x))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
n = I()
l = LI()
l.sort()
ans = 0
for i in range(n):
    ans += l[2*i]
print(ans)
"""

#B
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n,x = LI()
print((n-gcd(n,x))*3)
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
p = n
if x * 2 > n:
  x = n - x
ans = 0
while(x > 0):
  if n == p:
    ans += 3 * x * (n // x - 1)
  else:
    ans += 3 * x * (n // x)
  n, x = x, n % x
print(ans)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())

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

k = gcd(n,x)
if k == 1:
    print((n-1)*3)
else:
    print((int(n/k)-1)*3*k)

Submission status: Accepted

Solution code:
def main():
    n,x=map(int,input().split())
    a,b=n-x,x
    if(a<b):
       a,b=b,a
    path_length = calc_path(a,b,n)
    print(path_length)

def  calc_path(a1,b1,c1):
    q , mod=divmod(a1,b1)
    count=0
    if mod==0:
         c2=c1+2*b1*q-b1
         return c2
    else:
        count=count+1
        c2=c1+2*b1*q
        a2=a1-b1*q
        b2=b1
        if(a2<b2):
           a2,b2=b2,a2
        return calc_path(a2,b2,c2)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)


n,x = map(int,input().split())

g = gcd(n,x)

n //= g

print((3*n-3)*g)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, x = LI()

    b, a = sorted([x, n - x])
    ans = a + b
    while b:
        q, mod = divmod(a, b)
        ans += (2 * q - (not mod)) * b
        a, b = b, mod

    return ans


print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N, X = map(int, input().split())


def rec(a, b):
    a, b = min(a, b), max(a, b)
    if b % a == 0:
        return (2 * a) * (b // a) - a
    else:
        return (2 * a) * (b // a) + rec(a, b % a)


print(X + N - X + rec(X, N - X))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
x = min(x,n-x)
n = n - x
ans = 0
while True:
  new_x = n%x 
  new_n = n//x
  if new_x ==0:
    print(ans+x*new_n*3)
    exit()
  else:
    ans = ans + x*new_n*3
    n = x
    x = new_x

Submission status: Accepted

Solution code:
def solve(s, a, b):
    if a % b == 0:
        return s + ((a // b) * 2 - 1) * b
    if b % a == 0:
        return s + ((b // a) * 2 - 1) * a
    elif a > b:
        s += (a // b) * 2 * b
        return solve(s, a % b, b)
    else:
        s += (b // a) * 2 * a
        return solve(s, a, b % a)

n, x = map(int, input().split())
print(solve(n, n - x, x))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())

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

ans = 3*(n-g(n, x))
print(ans)

Submission status: Accepted

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

n, x = map(int, input().split())
print(3*(n - gcd(n, x)))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
if (x > n // 2 and n % 2 == 0) or (x > (n + 1) // 2 and n % 2 == 1):
    x = n - x

A = n - x
B = x
k = 0
m = -1
ans = n
while m != 0:
    k = A // B
    m = A % B
    ans += B * k * 2
    if m == 0:
        ans -= B
    A = B
    B = m

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
from math import floor
n,x=map(int,input().split())
ans=0
def f(x,y):
    if y%x==0:
        return (y//x-1)*2*x+x
    return 2*x*(y//x)+f(y%x,x)
print(n+f(min(x,n-x),max(x,n-x)))

Submission status: Accepted

Solution code:
import fractions

n,x = (int(i) for i in input().split())
ans = fractions.gcd(n,x)
print(3*(n-ans))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
l = 0

if X < N-X:
  long = N - X
  short = X
else:
  long = X
  short = N - X
l += N
while True:
  l += long // short * short * 2
  x = long % short
  if x == 0:
    l -= short
    break
  long = short
  short = x
  
print(l)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

li = [int(i) for i in input().split(" ")]
res = (li[0] // gcd(li[0], li[1]) -1) * 3 * gcd(li[0], li[1])
print(res)

Submission status: Accepted

Solution code:
N, X = map( int, input().split())
a, b = max(X, N-X), min(X, N-X) #a >= b
ans = a + b
if a == b:
    ans += a
while a != b:
    if a%b == 0:
        ans += (a//b*2-1)*b
        break
    ans += a//b*2*b
    a, b = b, a%b
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())

# a <= b
def f(a, b):
    if b % a == 0:
        return (b // a) * 2 * a - a
    return (b // a) * a * 2 + f(b % a, a)

print(n + f(min(x, n - x), max(x, n - x)))

Submission status: Accepted

Solution code:
from fractions import gcd
n,x=map(int,input().split())
print(3*(n-gcd(n,x)))

Submission status: Accepted

Solution code:
N,X = map(int,input().split())

def f(a,b) :
    if a > b :
        a,b = b,a
    if b % a == 0 :
        return 2*(b//a-1)*a + a
    else :
        return 2*(b//a)*a + f(a,b%a)
        
ans = N + f(X,N-X)

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

def rec(a: int, b: int) -> int:
    mx = max(a,b)
    mn = min(a,b)
    if gcd(a,b) == mn:
        return (2 * (mx // mn) - 1) * mn
    
    else:
        return (2 * (mx // mn) * mn)  + rec(mn, mx - mn * (mx // mn))
    
n,x = li()
print(n + rec(x, n-x))

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
ans = N
a,b = X,N-X
if a>b: a,b = b,a
while a:
    d,m = divmod(b,a)
    ans += d*a*2
    a,b = m,a
    if a>b: a,b = b,a
ans -= b
print(ans)

Submission status: Accepted

Solution code:
# your code goes here
from math import floor
N, X = [int(x) for x in input().split()]

y = N-X
x = X
L = X
while x > 0:
#	k = 2*floor(y/x)
	k, z = divmod(y, x)
#	dL = x*(2*k-1)+y
	L += x*(2*k-1)+y
#	print(x, y, k, dL)
	y, x = (x, z)

#L += y
print(L)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

def f(a,b):
    if a==b:return a
    if not a<b:a,b=b,a
    return 2*(b//a)*a+f(a,b%a) if b%a else 2*(b//a)*a-a

N,X=map(int,input().split())
print(f(X,N-X)+N)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
TotalLength = N

Vert = N-X
Hor = X
Fin = False
while not Fin:
    if Vert < Hor:
        if Hor % Vert == 0:
            TotalLength += (2 * (Hor//Vert) - 1) * Vert
            Fin = True
        else:
            TotalLength += 2 * (Hor//Vert) * Vert
            Hor %= Vert
    else:
        if Vert % Hor == 0:
            TotalLength += (2 * (Vert//Hor) - 1) * Hor
            Fin = True
        else:
            TotalLength += 2 * (Vert//Hor) * Hor
            Vert %= Hor
print(TotalLength)

Submission status: Accepted

Solution code:
n, a = map(int, input().split(' '))
b = n - a
if a < b:
    a, b = b, a
ans = n
while b:
    q = a // b
    ans += 2 * q * b
    a %= b
    a, b = b, a
ans -= a
print(ans)

Submission status: Accepted

Solution code:
# %%time
import numpy as np
n, x = list(map(int, input().split()))
s = 0
a = [n-x, x]
s += n
# print(a,s)
while True:
#     if a[0] == a[1]:
#         s += a[0]
#         break
#     else:
    mi = np.min(a)
    ar = np.argmax(a)
    num = a[ar]//mi
    a[ar] -= mi * num
    s += 2 * mi * num
#     print(a, s)
    if np.min(a) == 0:
        s -= mi
        break
            
print(s)

Submission status: Accepted

Solution code:
def f(a, b):
	if a > b:
		a, b = b, a
	if a == 0:
		return -b
	return 2*(b/a)*a + f(a, b%a)
n, x = map(int, raw_input().split())
print n + f(n-x, x)

Submission status: Accepted

Solution code:
#最大公約数
def gcd(a,b):
    if a==b:
        return b
    elif a%b== 0:
        return b
    else:
        return gcd(b,a%b)

import math

def func(a,b):
    if a<=b :
        if b%a != 0:
            return 2*math.floor(b/a)*a+func(a,b%a)
        else:
            return 2*(math.floor(b/a))*a-a
    else:
        return func(b,a)
N,X = map(int,input().split())

dis =N 
dis += func(N-X,X)
dis1 = 3*(N-gcd(N,X))
print(dis)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
ans = 0
if 2*x == n:
    ans = 3*x
else:
    ans += n
    a = x
    b = n - x
    while True:
        ans += (a//b)*2*b
        c = b
        b = a%b
        a = c
        if b == 0:
            ans -= a
            break
    
print(ans)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
ans = 0
if 2*x == n:
    ans = 3*x
else:
    ans += n
    a = x
    b = n - x
    while True:
        ans += (a//b)*2*b
        c = b
        b = a%b
        a = c
        if b == 0:
            ans -= a
            break
    
print(ans)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
ans = N
a,b = X, N-X
if a > b: a,b = b,a
while b:
    d,m = divmod(a,b)
    ans += 2*b*d
    a,b = b,m
ans -= a
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
ans = N
a, b = sorted((X, N - X))
while a != 0:
    if b % a == 0:
        ans += 2 * (b // a - 1) * a + a
        print(ans)
        break
    else:
        ans += 2 * (b // a) * a
        a, b = sorted((a, b % a))

Submission status: Accepted

Solution code:
def f(n, x):
    if n % x == 0:
        return (n // x * 2 - 1) * x
    else:
        return (n // x * 2) * x + f(x, n % x)
n, x = map(int,input().split())
ans = n + f(n - x, x)
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
ans = N
a, b = sorted((X, N - X))
while a != 0:
    if b % a == 0:
        ans += 2 * (b // a - 1) * a
        break
    else:
        ans += 2 * (b // a) * a
        a, b = sorted((a, b % a))
print(ans + a)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())

def f(x,y):
  if x%y==0:
    return y*(2*x//y-1)
  else:
    res=0
    res=y*2*(x//y)+f(y,x%y)
    return res

print(f(N-X,X)+N)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())

res = n
a = x #横
b = n-x #縦


while True:
    if a == b:
        res += a
        break
    elif a > b:
        k = a//b
        c = a%b
        if c == 0:
            res += (2*k-1)*b
            break
        else:
            res += 2*k*b
            a = c
    else:
        k = b//a
        c = b%a
        if c == 0:
            res += (2*k-1)*a
            break
        else:
            res += 2*k*a
            b = c
           

print(res)

Submission status: Accepted

Solution code:
"""取込"""
n, x = [int(i) for i in input().split(" ")]

"""問題"""
def f(a, b):
    # print("({0}, {1})".format(a, b))
    l = max(a, b)
    s = min(a, b)
    if s == 0:
        return -l
    else:
        return (l // s) * s * 2 + f(l % s, s)

d = n + f(n - x, x)

"""出力"""
print(d)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def light_length(a:int, b:int) -> int:
    if a > b:
        a,b = b,a
    
    if b%a == 0:
        return 2 * a * (b//a) - a

    return 2 * (b//a) * a + light_length(a, b%a)

n,x = li()

print(n + light_length(x,n-x))

Submission status: Accepted

Solution code:
N,X = map(int,input().split())

a,b = X,N-X
if a > b: a,b = b,a
ans = a+b

while b%a:
    ans += b//a * (2*a)
    a,b = b%a, a
ans += b//a * (2*a) - a

print(ans)

Submission status: Accepted

Solution code:
N, X = [int(i) for i in input().split()]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
scale = gcd(N, X)
print(scale*(N//scale-1)*3)

Submission status: Accepted

Solution code:
N, X = [int(elem) for elem in input().split()]
total_distance = N
bigger, smaller = N - X, X
while bigger % smaller != 0:
    total_distance += 2 * (bigger // smaller) * smaller
    bigger, smaller = smaller, bigger % smaller

total_distance += 2 * (bigger // smaller) * smaller - smaller
print(total_distance)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m=map(int,input().split())
print(3*(n-gcd(n,m)))

Submission status: Accepted

Solution code:
ai = lambda: list(map(int,input().split()))

n, x = ai()
from fractions import gcd
print(3*(n-gcd(n,x)))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
import fractions
print(3 * (n-fractions.gcd(n,x)))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
ans = N
a, b = min(X, N - X), max(X, N - X)
while b % a:
    ans += 2 * (b // a) * a
    a, b = b % a, a
ans += 2 * b // a * a - a
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())

ans = n

longer = max(x, n-x)
shorter = min(x, n-x)

while True:
    m = longer // shorter
    l = longer % shorter
    ans += m*shorter*2
    if l == 0:
        ans -= shorter
        break
    longer = shorter
    shorter = l
    
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N,X = map(int,input().split())
print(3*(N-gcd(N,X)))

Submission status: Accepted

Solution code:
# coding:utf-8


def inpl(): return list(map(int, input().split()))


n, x = inpl()


def func(a, b):
    if a < b:
        a, b = b, a
    if a == b:
        return a
    else:
        if a % b == 0:
            return (a // b * 2 - 1) * b
        else:
            q, mod = divmod(a, b)
            return 2 * q * b + func(b, mod)
            # return 2*b + func(a-b, b)#再帰回数が10000を超えるとエラー(20000000001, 4)など


if x == n / 2:
    print(3 * x)
else:
    print(n + func(x, n - x))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
path = N
a, b = X, N - X
if a < b:
    a, b = b, a
while b > 0:
    path += b * (a // b) * 2
    a, b = b, a % b
path -= a
print(path)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
ans = n
n -= x
while n % x != 0:
	ans += 2 * (n // x) * x
	n , x = x, n % x
ans += 2 * (n // x) * x - x
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

[N, X] = list(map(int, input().split()))
print(int(3*(N-gcd(N,X))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    if N % 2 == 0 and X == N//2:
        return 3*X
    ans = 0
    if X > N//2:
        X = N-X

    ans = X

    def f(n, x):
        # print(n, x)
        ans = 0
        ans += n
        n_x = n // x
        ans += 2*n_x*x - x
        if n % x != 0:
            ans += f(x, n - n_x*x)

        # print(n, x, n_x, 2*n_x*x - x, ans)
        return ans

    return ans + f(N-X, X)


def main():
    N, X = read_int_n()
    print(slv(N, X))

  

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
D=N
L=N-X
S=X
if N==2*X:
    D=3*X
else:
    for i in range(100):
        
        if L%S==0:
            D=D+(2*S)*(L//S)-S
            break
        else:
            D=D+(2*S)*(L//S)
            A=L
            B=S
            L=B
            S=A%B
            #print(D)
print(D)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())

ans = N
if X >= N - X:
    a, b = X, N - X
else:
    a, b = N - X, X

while b > 0:
    ans += (a // b) * b * 2
    a, b = b, a % b
ans -= a

print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())

def func(a, b):
    if a < b:
        if b%a == 0:
            return (b//a*2 - 1)*a
        else:
            q, mod = divmod(b,a)
            return 2*q*a + func(a, mod)
    elif a > b:
        if a%b == 0:
            return (a//b*2 - 1)*b
        else:
            q, mod = divmod(a,b)
            return 2*q*b + func(mod, b)
    else:
        return a

if x == n/2:
    print(3*x)
else:
    print(x+(n-x)+func(x,n-x))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
def calc(d, c):
    q, m = divmod(d, c)
    if m == 0:
        return (2*q-1)*c
    else:
        return calc(c, m) + 2*q*c
print(N + calc(X, N-X))

Submission status: Accepted

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**8)


#最大公約数
def gcd(a,b):
	while b:
		a,b = b, a%b
	return a
	
#最小公倍数
def lcm(a,b):
	return a*b // gcd(a,b)



N,X = map(int,input().split())

ans = N

a = min(X,N-X)
b = max(X,N-X)

while True:	#a<b
	n = b//a 
	ans += n * 2 * a
	
	if n*a == b:
		ans -= a
		print(ans)
		sys.exit()
		
		
	a, b = b-n*a, a

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy
# sys.setrecursionlimit(1000000)

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def gcd(x, y):
    if x < y:
        x, y = y, x  # x >= y
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

def main():
    n, x = map(int, input().split())
    print(3 * (n - gcd(n, x)))

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

sys.setrecursionlimit(100000)

N, X = map(int, input().split())

def f(x, n):
    if x == 0 or x == n:
        return 0
    debug(x,n)
    # if 2*x == n:
    #     return 3*x
    if x % (n-x) == 0:
        return 3*x
    if 2*x < n:
        # return f(x, n-x) + 3*x# n + x
        return f(n-x, n)
    a = x//(n-x) + 1
    t = a*(n-x) - x
    return f(n-x-t, n-x) + 3*x # + t

print(f(X, N))

Submission status: Accepted

Solution code:
from fractions import gcd
N, X = map(int, input().split())
print(3 * (N - gcd(N, X)))

Submission status: Accepted

Solution code:
lst=list(map(int,input().split()))
#x n-x x x n-2x n-2x n-2x
n=lst[0]
x=lst[1]
#if x==n-x :
#    s=
if n-x<=x:
    a,b=x,n-x
else:
    a,b= n-x,x
s=n
#i=0
while b!=0:
    s+=a//b*2*b
    c=a
    a=b
    b=c%b
print(s-a)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())

a = X
b = N-X
ans = a+b
while b:
    d,m = divmod(a,b)
    ans += d*b*2
    a,b = b,m
print(ans - a)

Submission status: Accepted

Solution code:
n,x = (int(i) for i in input().split())
ans,a,b = n,x,n-x
while a%b!=0: ans,a,b = ans+(a//b)*2*b,b,a%b
print(ans+2*a-b)

Submission status: Accepted

Solution code:
n, x = input().split()
n = int(n)
x = int(x)
ans = 0
a1, a2 = x, n - x
l = min(a1, a2)
h = max(a1, a2)
while True:
    d = h // l
    ans += 3 * l * d
    temp = h - l * d
    if temp == 0:
        break
    h = l
    l = temp
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())

def aaa(a,b):
    n = max(a,b)
    m = min(a,b)
    if n % m == 0:
        return 2 * n - m
    else:
        return 2 * m * int(n / m) + aaa(m, n % m)

ans = n + aaa(n-x, x)

print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())

def solve(a,b):
  mi=min(a,b)
  ma=max(a,b)
  if ma%mi==0:
    return (ma//mi*2-1)*mi
  else:
    return (ma//mi*2)*mi+solve(mi,ma%mi)

ans=n+solve(n-x,x)
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)
N,X=map(int,input().split())
print(3*(N-gcd(N,X)))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


print(3*(N - gcd(N, X)))

Submission status: Accepted

Solution code:
def gcd(a, b):
        while a != b:
                if a == 0:
                        return b
                elif b == 0:
                        return a
                if a > b :
                        a %= b
                else:
                        b %= a
        return a

N, X=map(int, input().split())

print(3*(N - gcd(N, X)))

Submission status: Accepted

Solution code:
def solve(x, y):
    a = max(x, y)
    b = min(x, y)
    if b == 0:
        return 0
    res = 2*a
    r = solve(b-a % b, a % b)
    if r == 0:
        res -= b
    res += r
    return res


s = raw_input().split()
n = int(s[0])
x = int(s[1])

ans = n + solve(x, n-x)
print(ans)

Submission status: Accepted

Solution code:
def calc(a, b):
    if a <= 0 or b <= 0:
        return 0
    if a == b:
        return a
    a, b = min(a, b), max(a, b)
    x = max(1, b / (2 * a))
    return calc(b-x*a, a) + 2 * a * x

N, X = map(int, raw_input().split())
print calc(X, N-X) + N

Submission status: Accepted

Solution code:
n, x = map(int, raw_input().split())
a, b, result = x, n - x, n
while b != 0:
    result += 2 * (a // b) * b
    a, b = b, a % b
print result - a

Submission status: Accepted

Solution code:
n, x = map(int, raw_input().split())
z = n
y = n - x
while y > 0:
	z += x / y * y * 2
	x, y = y, x % y
print z - x

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, X = map(int, input().split())
    print(3 * (N - gcd(N, X)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(a, b):
    if a * b == 0:
        return 0
    res = f(min(a, b), max(a, b) % min(a, b)) + 2 * min(a, b) * (max(a,b)//min(a, b))
    if(max(a, b) % min(a, b) == 0):
        res -= min(a, b)
    return res

n, x = map(int, input().split())
res = n + f(n - x, x)
print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,x = LI()
    return 3 * (n-fractions.gcd(n,x))


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def f(n, x):
    if n % x == 0:
        return (n // x * 2 - 1) * x
    else:
        return (n // x * 2) * x + f(x, n % x)
n, x = map(int,input().split())
ans = n + f(n - x, x)
print(ans)

Submission status: Accepted

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



N,k = map(int,raw_input().split())
#k = int(raw_input())
#A = map(int, raw_input().split())
ans = gcd(N,k)
print 3*(N - ans)

Submission status: Accepted

Solution code:
def solve(a,b):
	a,b = max(a,b),min(a,b)
	if b == 0:
		return 0
	res = 2*a
	r = solve(b-a%b, a%b)
	if r == 0:
		res -= b
	res += r
	return res
	
n,x = map(int, raw_input().split())

ans = n + solve(x, n-x)
print ans

Submission status: Accepted

Solution code:
#ABC001B

def gcd(a, b):
 while b:
  a, b = b, a % b
 return a

n,x=map(int,raw_input().split())
res=3*(n-gcd(n,x))
print res

Submission status: Accepted

Solution code:
n,x=map(int,raw_input().split())
def gcd(i,j):
    if j==0:return i
    else:return gcd(j,i%j)
print 3*(n-gcd(n,x))