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())

def func(a, b):
    if a < b:
        a, b = b, a

    res = 0
    while b > 0:
        c, d = divmod(a, b)
        res += 2 * b * c
        a = b
        b = d
    
    return res - a

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

Submission status: Accepted

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

def func(a, b):
    res = 0
    while b > 0:
        c, d = divmod(a, b)
        res += 2 * b * c
        a = b
        b = d
    
    return res - a

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

Submission status: Accepted

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

def func(a, b):
    res = 0
    while b > 0:
        c, d = divmod(a, b)
        res += 2 * b * c
        a = b
        b = d
    
    return res - a

if n == 2 * x:
    print(3 * x)
elif n > 2 * x:
    print(n + 2 * x + func(max(x, n-2*x), min(x, n-2*x)))
else:
    print(n + func(x, n-x))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, x = map(int, input().split())
    n -= x
    res = 0
    while x != 0:
        q, r = divmod(n, x)
        res += q * x * 3
        n = x
        x = r
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

def solve(n,x):
    res = 3 * (n - gcd(n,x))
    return res



if __name__ == '__main__':
    n,x = map(int,input().split())
    print(solve(n,x))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
ans += n

l1, l2 = min(n - x, x), max(n - x, x)
#while True:
#    if l1 == l2:
#        ans += l1
#        break
#    else:
#        ans += (l1 * 2)
#        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)
#while True:
#    if l2 % l1 == 0:
#        ans += (l1 * ((l2 // l1) * 2 - 1))
#        break
#    else:
#        ans += (l1 * 2)
#        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)
while True:
    if l2 % l1 == 0:
        ans += (l1 * ((l2 // l1) * 2 - 1))
        break
    else:
        ans += (l1 * 2) * (l2 // l1)
        l1, l2 = l2 % l1, l1

print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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


def f(a, b):
    if a == b:
        return a
    if a > b:
        a, b = b, a
    if b % a == 0:
        return 2 * b - a
    else:
        div, mod = divmod(b, a)
        return 2 * a * div + f(a, mod)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x = map(int, input().split())
v0 = n
v1 = n-x
ans = x
init = 0
while True:
    num, amari = divmod(v0,v1)
#     print(ans, v0,v1)
    if amari==0:
        ans += (2*(num-1)+init)*v1
        break
    else:
        ans += (2*(num-1)+1+init)*v1
        v0,v1 = v1,amari
    if init == 0:
        init = 1
print(ans)

Submission status: Accepted

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


def solution(N, X):
  if N<X:
    N, X = X, N
  if not N % X:
    return (2*(N//X) -1) * X
  else:
    return 2*(N//X)*X + solution(X, N%X)
      
answer = solution(N-X, X) + N
print(answer)

Submission status: Accepted

Solution code:
N,X = input().split()
N,X = int(N), int(X)
answer = X+ (N-X)


def rhombus(N,X):
  	
    if X==1: 
        return N*2-1
    if X==0:
        return 0

    if N%X == 0:
        return X*(N//X)*2-X
      
    else: 
        k = N//X
        return k*2*X + rhombus(X,N-(k*X))

      

answer = answer + rhombus(N-X,X)
print(answer)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def f(a, b):
    if a == 0 or b == 0:
        return 0
    if a > b:
        q, r = divmod(a, b)
        return 2*q*b + f(a % b, b)
    else:
        return a+b+f(b-a, a)

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

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

Submission status: Accepted

Solution code:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, X = ZZ()
    N -= X
    ans = 0
    while True:
        ans += (N//X) * 3 * X
        #割り切れない
        if N%X: N, X = X, N%X
        #割り切れる
        else: break
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
res = N
a,b = max(N-X,X),min(N-X,X)

while b:
  q = a // b
  r = a % b
  res += (b*2)*q
  if r == 0: res -= b

  a,b = b,r

print(res)

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 (b // a * 2 - 1) * a
    return b // a * 2 * a + f(b % a, a)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def reflect(A, B):
    if A > B:
        A, B = B, A

    ref = B // A
    if B % A == 0:
        return (ref * 2 - 1) * A
    else:
        return ref * 2 * A + reflect(B % A, A)


N, X = map(int, sys.stdin.readline().rstrip().split())
print(N + reflect(X, N - X))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = n - x
b = x
ans = 0
while b:
    d, m = divmod(a, b)
    ans += d * b * 3
    a = b
    b = m
print(ans)

Submission status: Accepted

Solution code:
import math
N, X = list(map(int, input().split(' ')))
def f(a, b):
    a, b = min([a, b]), max([a, b])
    if b % a == 0:
        return 2 * a * math.floor(b / a) - a
    return 2 * a * math.floor(b / a) + f(a, b % a)
print(N + f(N - X, X))

Submission status: Accepted

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


if __name__ == "__main__":
    N, X = map(int, input().split())
    ans = 3 * (N - GCD(N, X))
    print(ans)

Submission status: Accepted

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

if X * 2 == N:
    ans = 3 * X
else:
    ans = 0
    if X * 2 < N:
        LL = N - X
        SS = X
    else:
        LL = X
        SS = N - X
    while True:
        div, mod = divmod(LL, SS)
        ans += 3 * SS * div
        if mod == 0:
            break
        LL = SS
        SS = mod

print(ans)

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))

a = K
b = N - K
c = 0
d = min(a, b)
while not a == b == c:
    a, b, c = sorted([a, b, c])
    if a != b:
        d = b - a
    cnt = (c - b) // d
    b += d * cnt
    a += d * cnt + d
print(a + b + c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, X = map(int, input().split())
def solve(n, x):
  #print(n, x)
  if n == 0:
    return 0
  if x == 1: return n * 3
  m = x
  y = n - n // x * x
  if y == 0: return n // x * x * 3
  return solve(m, y) + n // x * x * 3
print(solve(max(N - X, X), min(N - X, X)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
# from math import gcd
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n,x = myinput()

def mycalc(a,b):
    if b==0:
        return 0
    else:
        return ( (a//b) * 3 * b ) + mycalc(b,a%b)

ans = mycalc(n-x,x)
print(ans)

Submission status: Accepted

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

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

ans = N + f(X, N-X)

print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=max(n-x,x)
b=min(n-x,x)
s=n
while b!=0:
  c=a//b
  d=a%b
  s+=2*b*c
  if d==0:
    s-=b
  a=b
  b=d
print(s)

Submission status: Accepted

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def examA():
    N = I()
    L = LI()
    L.sort()
    ans = sum(L[::2])
    print(ans)
    return

def examB():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    N, X = LI()
    ans = 3*(N - gcd(N-X,X))
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examB()

"""

"""

Submission status: Accepted

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

ans = n
while True:
    c = max(a,b)
    d = min(a,b)
    if c % d != 0:
        ans += (c // d) * 2 * d
    else:
        ans += ((c // d) * 2 - 1) * d 
        break
    
    a = d
    b = c%d
    
print(ans)

Submission status: Accepted

Solution code:
# 解説AC

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

ans = N
a, b = max(N - X , X), min(N - X, X)
# Euclidの互除法
while b:
    q, r = divmod(a, b)

    ans += (b * 2) * q
    if r == 0: ans -= b # 最後

    a, b = b, r

print(ans)

Submission status: Accepted

Solution code:
import fractions

N, X = map(int,input().split())
GCD = fractions.gcd(N, X)

print(GCD*3*(N//GCD-1))

Submission status: Accepted

Solution code:
N,X=map(int, input().split())
ans=X
R,E=X,N-X
while True:
    ans+=R//E*E*2
    R-=R//E*E
    if not R: break
    ans+=E+R
    R,E=E-R,R
print(ans)

Submission status: Accepted

Solution code:
#B
n,x = [int(i) for i in input().split()]
ans = x
a = x
p = n-x
while(1):
    q,r = divmod(a,p)
    ans += p * 2* q
    if r==0:
        print(ans)
        break
    else:
        ans += p
        ans += r
        a = p -r 
        p = r

Submission status: Accepted

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

print(int(3*(N-fractions.gcd(N,X))))

Submission status: Accepted

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

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

S = N

a = N - X
b = X

while b > 0:
    c = a%b
    S += 2*(a-c)
    a,b = b,c

print(S-a)

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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10**10
def bfs(graph, visited, position, root):
    visited[root] = 1
    position[root] = 0
    deq = deque([root])
    while(deq):
        cur = deq.pop()
        # print(cur)
        for nxt, dist in graph[cur]:
            if position[cur] + dist != position[nxt]:
                if position[nxt] != INF:
                    return False
                else:
                    position[nxt] = position[cur] + dist
            if not visited[nxt]:
                deq.append(nxt)
                visited[nxt] = 1

    return True

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

    ans = n
    mx, mn = x, n - x
    if mx < mn:
        mx,mn = mn, mx

    # print(mx, mn)

    while(True):
        if mx % mn == 0:
            ans += 2 * mn * (mx // mn) - mn
            break
        else:
            ans += mn * 2 * (mx // mn)
            mx, mn = mn, mx % mn

    print(ans)


if __name__ == "__main__":

    main()

Submission status: Accepted

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

from fractions import gcd
print(3 * ( N - gcd(N, X)))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
ans = n
y, x = n-x, x
if x > y:
  y, x = x, y
while True:
  q, r = divmod(y, x)
  if r == 0:
    ans += (2*q-1)*x
    break
  ans += 2*q*x
  y, x = x, r
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:
n,x = map(int,input().split())
ans = n
A = x
B = n-x
while A and B:
  if A<B:
    A,B = B,A
  k = A//B
  if A%B:
    ans += k*B*2
  else:
    ans += B*(k*2-1)
  A = A%B
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def F(A,B):
    # (A,B)の平行四辺形の120度の対角から出た状態
    if A > B:
        A,B = B,A
    q,r = divmod(B,A)
    if not r:
        return A * (q+q-1)
    return F(A,r) + q * (2 * A)

answer = N + F(X,N-X)
print(answer)

Submission status: Accepted

Solution code:
def run():
  N, X = map(int, input().split())
  y = N-X
  ans = N
  while True:
    y, X = max(y, X), min(y, X)
    a = y//X
    b = y%X
    ans += a*X*2
    if b == 0:
      break
    y, X = X, b
  print(ans-X)
  
  
if __name__ == '__main__':
  run()

Submission status: Accepted

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


main()

Submission status: Accepted

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

length = n
n=n-x
while True:
    t=n//x
    length+=2*t*x
    a=n
    n=x
    x=a-t*x
    if x==0:
        length-=n
        break
print(length)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import sqrt

def solve(N: int, X: int):
    # 平行四辺形の面積
    answer = N
    a,b = max(N-X,X),min(N-X,X)
    while True:
        answer += 2*(a//b)*b
        if a%b == 0:
            answer -= b
            break
        a,b = b,a%b

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N,X = map(int,input().split())
ans = 0
oldx = 0

if N > 2 * X:

    ans = N
    N = N - X

elif N == 2 * X:
    ans = 3 * X
    print (ans)
    sys.exit()

else:

    ans = N
    oldx = X
    X = N - X
    N = oldx

while True:

    #print (N,X,ans)

    if N % X == 0:
        ans += ((N // X) * 2 - 1) * X
        break

    else:
        ans += ((N // X) * 2 * X)

        oldx = X
        X = N % X
        N = oldx

    

print (ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
ans = N
a, b = max(X, N-X), min(X, N-X)
while b:
    q, r = divmod(a, b)
    if r == 0:
        ans += b * (2 * q - 1)
    else:
        ans += b * 2 * q
    a, b = max(b, r), min(b, r)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X = MAP()

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

Submission status: Accepted

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

ans = N

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

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

print ans

Submission status: Accepted

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


def solve(edge, width, ans):
	a, b = divmod(width, edge)
	if b == 0:
		return ans+edge*(2*a-1)
	return solve(width-edge*a, edge, ans + edge*2*a)

print(solve(min(X,N-X), max(X, N-X), N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import fractions
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n,x = MAP()

def cal(a,b):
    if a > b:
        aa = a
        a = b
        b = aa
    ref = b//a
    if b%a == 0:
        return a*(2*ref-1)
    return a*2*ref + cal(b%a,a)

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

Submission status: Accepted

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

ans = 0
def rec(a,b):
    global ans
    if a > b:
        a,b = b,a
    if b%a == 0:
        k = b//a
        ans += (2*k-1)*a
    else:
        k = b//a
        ans += 2*k*a
        rec(a, b%a)
ans += n
rec(n-x,x)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
INF = 10**10
MOD = 10**9+7

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, X = MAP()

# 最初のN以外は、平行四辺形を小さくしていくと考える
def rec(a, b):
    if b == 0:
        # 最後に割り切れた時は半分でいいので減らす
        return -a
    a, b = min(a, b), max(a, b)
    # 同じだけ小さくする所はまとめてやる
    return a*2*(b//a) + rec(a, b%a)

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,x=map(int,input().split());print((n-gcd(n,x))*3)

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,x=map(int,input().split());print((n-gcd(n,x))*3)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, X = MAP()

# 最初のN以外は、平行四辺形を小さくしていくと考える
def rec(a, b):
    a, b = min(a, b), max(a, b)
    if a == 0:
        # 最後に割り切れた時は半分でいいので減らす
        return -b
    # 同じだけ小さくする所はまとめてやる
    return a*2*(b//a) + rec(a, b%a)

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

Submission status: Accepted

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

ans = n

wall_side = n - x
light_length = n - (n - x)
while True:
    if wall_side % light_length == 0:
        ans += (2 * (wall_side // light_length - 1) + 1) * light_length
        break
    else:
        ans += 2 * (wall_side // light_length) * light_length
        wall_side, light_length = light_length, wall_side % light_length
        

print(ans)

Submission status: Accepted

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

import sys
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, X = MAP()

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

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a, b = max(n-x,x),min(n-x,x)
res = a+b
while b!=0:
    q = a//b
    r = a%b
    res += (b*2)*q
    if (r==0):
        res -= b
    a, b = b, r

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, X = map(int, input().split())
    ans = N
    min_ = min(X, N-X)
    max_ = max(X, N-X)
    while min_ != 0:
        # print(max_, min_)
        ans += (max_ // min_) * 2 * min_
        tmp = max_ % min_
        max_ = min_
        min_ = tmp
    ans -= max_
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
q, p = sorted((N - X, X))

r = 1
while r:
    p, r = divmod(p, q)
    N += (2 * p - (r == 0)) * q
    p, q = q, r

print(N)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

def F(x,y):
    """
    x,yの平行四辺形。対角にたどり着くまでの距離
    """
    if x>y:
        x,y = y,x
    q,r = divmod(y,x)
    if r == 0:
        return (2*q-1)*x
    return 2*q*x + F(x,y%x)

answer = N + F(X,N-X)
print(answer)

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, X = map(int, input().split())

    ans = N
    A = max(N - X, X)
    B = min(N - X, X)

    while B:
        q = A // B
        r = A % B

        ans += B * 2 * q
        if r == 0:
            ans -= B

        A = B
        B = r

    print(ans)

sol()

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
ans=n
M=max(n-x,x)
m=min(n-x,x)
while(True):
  r=M%m
  q=int((M-r)/m)
  if(r==0):
    ans+=(2*q-1)*m
    break
  else:
    ans+=2*q*m
    M=m
    m=r
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,x=map(int,input().split())
q,p=sorted((a-x,x))
while q:
	a+=(p//q*2-(p%q<1))*q
	p,q=q,p%q
print(a)

Submission status: Accepted

Solution code:
a,x = map(int,input().split())
q,p = sorted((a-x,x))
r = 1
while r:
	p,r = divmod(p,q)
	a += (2*p-(r==0))*q
	p,q = q,r
print(a)

Submission status: Accepted

Solution code:
n,x=[int(i) for i in input().split()]
ans=n
a,b=min(x,n-x),max(x,n-x)
while a:
  c=b%a
  ans+=(b-c)*2
  a,b=c,a
ans-=b
print(ans)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
ans = N
x=X
y=N-X
if x<y:x,y=y,x
while y!=0:
    k = x//y
    ans += y*k*2
    x,y = y,x%y
ans -= x
print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
c=n
def sol(a,b):
    global c
    if a==b:c+=a
    elif a%b==0:c+=b*(2*(a//b)-1)
    elif b%a==0:c+=a*(2*(b//a)-1)
    elif a>b:
        c+=b*(a//b)*2
        sol(a-a//b*b,b)
    else:
        c+=a*(b//a)*2
        sol(a,b-b//a*a)
sol(x,n-x)
print(c)

Submission status: Accepted

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

ans = N
a = N - X
b = X
while a != b:
    if a >= b:
        a, b = b, a
    if b%a != 0:
        ans += 2 * a * (b//a)
        b = b%a
    else:
        ans += 2 * a * (b//a - 1)
        b = a
print (ans + a)

Submission status: Accepted

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

def f(x,y):
    a = min(x,y)
    b = max(x,y)    
    if a == 0:
        return 0
    elif b%a == 0:
        return 2*b-a
    else:
        return 2*a*math.floor(b/a) + f(a,b%a)

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

Submission status: Accepted

Solution code:

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

def main():
    hen, start=map(int,input().split())

    koyakusuu = gcd(hen, start)
    ans = koyakusuu * 3 * (hen // koyakusuu - 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, X = map(int, input().split()) # 横に2個

X = X if 2*X <= N else N - X
a = X
b = (N-X)//X
c = (N-X)%X
ans = 0
while True:
    ans += a*b*3
    if c == 0:
        break
    a, b, c = c, a//c, a%c

print(ans)

Submission status: Accepted

Solution code:
def trapizoid_light(side, bottom):
    if (bottom - side) % side == 0:
        return 2 * (bottom - side)
    next_side = bottom % side
    return 2 * ((bottom - side) // side * side) + side + next_side + trapizoid_light(next_side, side) 

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

if N % 2 == 0 and N // 2 == X:
    print(3 * X)
else:
    if X <= N // 2:
        print(2 * X + N - X + trapizoid_light(X, N - X))
    else:
        print(2 * (N - X) + X + trapizoid_light(N - X, X))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
def gcd(a,b):
    while a%b>0:
        a,b=b,a%b
    return b
g=gcd(N,X)
ans=g*3*(N//g-1)
print(ans)

Submission status: Accepted

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

    remainder = n - (2 * x)

    if remainder == 0:
        print(3 * x)
        return

    if remainder < 0:
        n, x = x, (n - x)
    else:
        n -= x

    ans = 0
    while True:
        num = n // x
        ans += (3 * x) * num
        rem = n % x
        if rem == 0:
            break
        n, x = x, rem
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def mysterious_light(N: int, X: int)->int:
    g = gcd(N, X)
    return 3 * max(N-g, g)


if __name__ == "__main__":
    N, X = map(int, input().split())

    ans = mysterious_light(N, X)
    print(ans)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
x = X
y = N-X
if x<y:
    x,y = y,x
res = N
while y>0:
    x,y = y,x
    m = x*(y//x)
    res += m*2
    y -= m
res -= x
print(res)