Problem:


Score : 100 points

Problem Statement

Takahashi is drawing a segment on grid paper.

From a certain square, a square that is x squares to the right and y squares above, is denoted as square (x, y).

When Takahashi draws a segment connecting the lower left corner of square (A, B) and the lower left corner of square (C, D), find the number of the squares crossed by the segment.

Here, the segment is said to cross a square if the segment has non-empty intersection with the region within the square, excluding the boundary.

Constraints

1 \leq A, B, C, D \leq 10^9

At least one of A \neq C and B \neq D holds.

Input

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

A B C D

Output

Print the number of the squares crossed by the segment.

Sample Input 1

1 1 3 4

Sample Output 1

4

Sample Input 2

2 3 10 7

Sample Output 2

8



Sample input:
1 1 3 4


Sample output:
4

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100)
def rec(h, w):
    if h==1 and w==1:
        return 1
    
    if h%2==0 and w%2==0:
        return 2*rec(h//2, w//2)
    elif h%2==0:
        return 2*(h//2+(w+1)//2-1)
    elif w%2==0:
        return 2*(w//2+(h+1)//2-1)
    else:
        return 2*((h+1)//2+(w+1)//2-1)

A, B, C, D = map(int, input().split())
H = abs(C-A)
W = abs(D-B)
print(rec(H, W))

Submission status: Wrong Answer

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

a, b, c, d = map(int, input().split())

if a == c or b == d:
    print(0)
    sys.exit(0)

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

x = abs(a - c)
y = abs(b - d)

_gcd = gcd(x, y)
x2 = x // _gcd
y2 = y // _gcd

import math

print((math.ceil(y2 / x2) * x2) * _gcd)

Submission status: Wrong Answer

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

a, b, c, d = map(int, input().split())

if a == c or b == d:
    print(0)
    sys.exit(0)

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

x = abs(a - c)
y = abs(b - d)

_gcd = gcd(x, y)
x2 = x // _gcd
y2 = y // _gcd

import math

print(x2, y2)
print((math.ceil(y2 / x2) * x2) * _gcd)

Submission status: Wrong Answer

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

a, b, c, d = map(int, input().split())

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

x = abs(a - c)
y = abs(b - d)

_gcd = gcd(x, y)
x2 = x // _gcd
y2 = y // _gcd

import math

print((math.ceil(y2 / x2) * x2) * _gcd)

Submission status: Wrong Answer

Solution code:
a,b,c,d = map(int, input().split())

def gcd(u,v):
  while v:
    u,v = v,u%v
  return u

s = c-a
t = d-b
u = gcd(s,t)
s //= u
t //= u
print(u*(s+t-1))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
p, q = abs(a - c), abs(b - d)
g = gcd(p, q)
p //= g
q //= g
if p < q:
    p, q = q, p
print(g * min(p, q) * ((p + q - 1) // q))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
a,b,c,d = map(int,input().split())
p, q = abs(a - c), abs(b - d)
g = gcd(p, q)
p //= g
q //= g
print(g * 2 * min(p, q))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import math
a, b, c, d = [int(item) for item in input().split()]
a = abs(a - c)
b = abs(b - d)
if a > b:
    a, b = b, a
g = gcd(a, b)
a //= g; b //= g

print(math.ceil(b / a) * a * g)

Submission status: Wrong Answer

Solution code:
import math
a, b, c, d = [int(item) for item in input().split()]
a = abs(a - c)
b = abs(b - d)

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

print(math.ceil(b / a) * a)

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
    if x%y==0:
        return y
    while x%y>0:
        x,y=y,x%y
    return y
a,b,c,d=map(int,input().split())
x,y=abs(a-c),abs(b-d)
g=gcd(x,y)
print(g*(x//g+y//d-1))

Submission status: Wrong Answer

Solution code:
import sys

a, b, c, d = list(map(int, sys.stdin.readline().strip().split(" ")))

right = max(a, c)
left = min(a, c)

k = (b-d)/(a-c)

res = 0
for xx in range(left, right):
    #print(x)
    x = xx - left
    current_y = (b-d) * (x/(a-c)) if x % (a-c) == 0 else k * x
    next_y =  (b-d) * (x/(a-c)) if  (x+1) % (a-c) == 0 else k * (x + 1)
    if x % (a-c) == 0 and (x+1) % (a-c) == 0:
        res += abs((next_y - current_y))
    res+=(int(abs(next_y - current_y)) + 1)

print(res)

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,raw_input().split())
x=abs(c-a)
y=abs(d-b)
z=min(x,y)
print(z<1or(y+x-1)/z)*z

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,raw_input().split())
x=abs(c-a)or 1
y=abs(d-b)or 1
z=min(x,y)
print(y+x-1)/z*z

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,raw_input().split())
x=abs(c-a)or 1
print((abs(d-b)or 1)+x-1)/x*x

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
	if b==0:return a
	return gcd(b,a%b)
a,b,c,d=map(int,input().split())
c-=a
d-=b
g=gcd(max(c,d),min(c,d))
j=int(c/g)
k=int(d/g)
print((j+k-1)*g)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
a, b, c, d = map(int, raw_input().split())
x, y = c-a, d-b
print x+y-gcd(x,y)

Submission status: Wrong Answer

Solution code:
a,b,c,d = map(int, raw_input().split())

x = c-a
y = d-b

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

e = gcd(x,y)
x /= e
y /= e

print (x+y-1) * e

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d = map(int,input().split())

c -= a
d -= b

c = abs(c)
d = abs(d)

k = d/c
co = 0
kkk = 0
for i in range(1,c+1):
	if i * d / c == i * d // c:
		kk = i * d // c
		co += kk - kkk
		kkk = kk
	else:
		kk = i * d // c + 1
		co += kk - kkk
		kkk = kk - 1

print(co)

Submission status: Accepted

Solution code:
from math import gcd
a,b,c,d=map(int,input().split())
if a==c or b==d:
    print(0)
    exit()
p=abs(a-c)
q=abs(b-d)
g=gcd(p,q)
p//=g
q//=g
print((p+q-1)*g)

Submission status: Accepted

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

a, b, c, d = map(int, input().split())

if a == c or b == d:
    print(0)
    sys.exit(0)

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

x = abs(a - c)
y = abs(b - d)

_gcd = gcd(x, y)
x2 = x // _gcd
y2 = y // _gcd

import math

print((x2 + y2 - 1) * _gcd)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split())
gcd=lambda a,b:gcd(b,a%b)if a%b else b
def 数学は最強也(a,b):
  q=gcd(a,b)
  return q*((a//q)+(b//q-1))
print(数学は最強也(abs(a-c),abs(b-d)))

Submission status: Accepted

Solution code:
a,b,c,d = map(int, input().split())
def gcd(u,v):
  while v: u,v = v,u%v
  return u
s = abs(c-a)
t = abs(d-b)
u = gcd(s,t)
print(u*((s+t)//u-1) if u else 0)

Submission status: Accepted

Solution code:
from fractions import gcd
a,b,c,d=map(int,input().split())
if abs(c-a)==0 or abs(d-b)==0:
  print(0)
else:
  x,y=abs(c-a),abs(d-b)
  g=gcd(x,y)
  print(x+y-g)

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, input().split())
ac = abs(a - c)
bd = abs(b - d)
if ac == bd:
  ans = ac
elif ac == 0 or bd == 0:
  ans = 0
else:
  ans = ac + bd - gcd(ac, bd)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import math
a, b, c, d = [int(item) for item in input().split()]
a = abs(a - c)
b = abs(b - d)
if a > b:
    a, b = b, a
g = gcd(a, b)
a //= g; b //= g

print((a + b - 1) * g)

Submission status: Accepted

Solution code:
import fractions
A, B, C, D = map(int, input().split())
X = abs(C-A)
Y = abs(D-B)
if X == 0 or Y == 0:
  print(0)
else:
  #(0,0),(X,Y)間にある格子点の数をまず数えます
  g = fractions.gcd(X, Y)
  print(X+Y-g)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a

a, b, c, d = [ int(v) for v in input().split() ]

if a == c:
    print(abs(b-d))
elif b == d:
    print(abs(a-c))
else:
    x, y = max(abs(a-c),abs(b-d)),  min(abs(a-c),abs(b-d))
    a = gcd(x,y)
    ux, uy = x // a, y // a

    print(a * (ux+uy-1))

Submission status: Accepted

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

from fractions import gcd

A,B,C,D = map(int,input().split())

dx = abs(A-C)
dy = abs(B-D)

g = gcd(dx,dy)
answer = (dx + dy) - g
print(answer)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x%y==0:
        return y
    while x%y>0:
        x,y=y,x%y
    return y
a,b,c,d=map(int,input().split())
x,y=abs(a-c),abs(b-d)
g=gcd(x,y)
print(g*(x//g+y//g-1))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


a,b,c,d = map(int,input().split())

c -= a
d -= b

c = abs(c)
d = abs(d)

ll = gcd(c,d)



k = d/c
co = 0
kkk = 0


print((c//ll + d//ll - 1)*ll)

Submission status: Accepted

Solution code:
a,b,c,d = (int(i) for i in input().split())
def gcd(x,y):
	if x%y==0: return y
	else: return gcd(y,x%y)
if a==c or b==d: ans = 0
else:
	n = gcd(abs(a-c),abs(b-d))
	e,f = abs(a-c)//n,abs(b-d)//n
	ans = (e+f-1)*n
print(ans)

Submission status: Accepted

Solution code:
import fractions
x1,y1,x2,y2 = map(int,input().split())
if x1 == x2 or y1 == y2:
    print(0)
    exit()

dx,dy = abs(x1-x2),abs(y1-y2)
g = fractions.gcd(dx,dy)
print(g * (dx//g + dy//g - 1))

Submission status: Accepted

Solution code:
import fractions
if __name__ == "__main__":
    A, B, C, D = map(int, input().split())
    A -= C
    B -= D
    W = abs(A)
    H = abs(B)
    if W == 0 or H == 0:
        print(0)
        exit()
    res = W + H - 1
    g = fractions.gcd(W, H)
    print(res - g + 1)

Submission status: Accepted

Solution code:
def gcd(a,b): return b if a%b==0 else gcd(b,a%b)
def main():
    a,b,c,d = map(int,input().split())
    h = abs(b-d)
    w = abs(c-a)
    if h==0 or w==0 : return 0
    m = gcd(max(h,w),min(h,w))
    return h+w-m

print(main())

Submission status: Accepted

Solution code:
import fractions

def main():
    a,b,c,d = map(int,input().split())
    a,c = min(a,c),max(a,c)
    b,d = min(b,d),max(b,d)

    c -= a
    a = 0
    d -= b
    b = 0

    if a==c or b==d:
        return 0

    g = fractions.gcd(c,d)
    c//=g
    d//=g
    ct = c+d-1
    return g*ct

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
c=abs(c-a)
d=abs(d-b)
g=fractions.gcd(c,d)
j=int(c/g)
k=int(d/g)
print((j+k-1)*g)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
c=abs(c-a)
d=abs(d-b)
g=fractions.gcd(max(c,d),min(c,d))
j=int(c/g)
k=int(d/g)
print((j+k-1)*g)

Submission status: Accepted

Solution code:
import fractions
a,b,c,d=map(int,input().split())
x=abs(c-a)
y=abs(d-b)
if x==0 or y==0:
    print(0)
else:
    gcd=fractions.gcd(x,y)
    m=x//gcd
    n=y//gcd
    print((m+n-1)*gcd)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import fractions
a, b, c, d = map(int, input().split())
h = abs(a - c)
w = abs(b - d)
if h == 0 or w == 0:
    ans = 0
else:
    h1 = h // fractions.gcd(h, w)
    w1 = w // fractions.gcd(h, w)
    ans = (h1 + w1 - 1) * fractions.gcd(h, w)
print(ans)

Submission status: Accepted

Solution code:
a,b,c,d=map(int,raw_input().split())
g=lambda m,n:g(n,m%n)if m%n else n
A=map(abs,[c-a,d-b])
A.sort()
print sum(A)-g(*A)

Submission status: Accepted

Solution code:
import math
import fractions
A, B, C, D = map(int, input().split())
if A == C or B == D:
    print(0)
    exit()

x = abs(A - C)
y = abs(B - D)

print(x + y - fractions.gcd(x, y))

Submission status: Accepted

Solution code:
def gcd(a,b):
	if b==0:return a
	return gcd(b,a%b)
a,b,c,d=map(int,input().split())
c=abs(c-a)
d=abs(d-b)
g=gcd(max(c,d),min(c,d))
j=int(c/g)
k=int(d/g)
print((j+k-1)*g)

Submission status: Accepted

Solution code:
from fractions import gcd
a, b, c, d = map(int, raw_input().split())
x, y = abs(c-a), abs(d-b)
if (x == 0 or y == 0):
    print 0
else:
    print x+y-gcd(x,y)

Submission status: Accepted

Solution code:
a,b,c,d = map(int, raw_input().split())

x = abs(c-a)
y = abs(d-b)

if x == 0 or y == 0:
	print 0
	import sys
	sys.exit(0)

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

e = gcd(x,y)
x /= e
y /= e

print (x+y-1) * e

Submission status: Runtime Error

Solution code:
from fraction import gcd
a,b,c,d=map(int,input().split())
if abs(c-a)==0 or abs(d-b)==0:
  print(0)
else:
  x,y=abs(c-a),abs(d-b)
  g=gcd(x,y)
  print(x+y-g)

Submission status: Runtime Error

Solution code:
import math
a,b,c,d=map(int,input().split())
x,y=abs(a-c),abs(b-d)
g=math.gcd(x,y)
print(g*(x//g+y//d-1))

Submission status: Runtime Error

Solution code:
import math
a,b,c,d=map(int,input().split())
x,y=abs(a-c),abs(b-d)
g=math.gcd(x,y)
print(g*(x//g+y//d-1))

Submission status: Runtime Error

Solution code:
import math
if __name__ == "__main__":
    A,B,C,D = map(int, input().split())
    A -= C
    B -= D
    W = abs(A)
    H = abs(B)
    if W == 0 or H == 0:
        print (0)
        exit()
    res = W + H - 1
    g = math.gcd(W, H)
    print (res - g + 1)

Submission status: Runtime Error

Solution code:
import math
if __name__ == "__main__":
    A,B,C,D = map(int, input().split())
    A -= C
    B -= D
    W = abs(A)
    H = abs(B)
    if W == 0 or H == 0:
        print (0)
        exit()
    res = W + H - 1
    g = math.gcd(W, H)
    print (res - g + 1)

Submission status: Runtime Error

Solution code:
import math

def main():
    a,b,c,d = map(int,input().split())
    a,c = min(a,c),max(a,c)
    b,d = min(b,d),max(b,d)

    c -= a
    a = 0
    d -= b
    b = 0

    if a==c or b==d:
        return 0

    g = math.gcd(c,d)
    c//=g
    d//=g
    ct = c+d-1
    return g*ct

if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math
a, b, c, d = map(int, input().split())
h = abs(a - c)
w = abs(b - d)
h1 = h // math.gcd(h, w)
w1 = w // math.gcd(h, w)
print((h1 + w1 - 1) * math.gcd(h, w))

Submission status: Runtime Error

Solution code:
import math
A, B, C, D = map(int, input().split())
if A == C or B == D:
    print(0)
    exit()

x = abs(A - C)
y = abs(B - D)

print(x + y - math.gcd(x, y))

Submission status: Runtime Error

Solution code:
import math
A, B, C, D = map(int, input().split())
if A == C or B == D:
    print(0)

x = abs(A - C)
y = abs(B - D)

print(x + y - math.gcd(x, y))

Submission status: Runtime Error

Solution code:
import math
a,b,c,d=map(int,input().split())
c-=a
d-=b
g=math.gcd(max(c,d),min(c,d))
j=int(c/g)
k=int(d/g)
print((j+k-1)*g)

Submission status: Runtime Error

Solution code:
import math
a,b,c,d=map(int,input().split())
c-=a
d-=b
g=math.gcd(c,d)
j=int(c/g)
k=int(d/g)
print((j+k-1)*g)

Submission status: Runtime Error

Solution code:
import math
a,b,c,d=map(int,input().split())
c-=a
d-=b
g=math.gcd(c,d)
j=c//g
k=d//g
print((j+k-1)*g)

Submission status: Runtime Error

Solution code:
import math
a,b,c,d=map(int,input().split())
c-=a;d-=b;
g=math.gcd(c,d)
j=c//g;k=d//g
print((j+k-1)*g)

Submission status: Runtime Error

Solution code:
a,b,c,d = map(int, raw_input().split())

x = abs(c-a)
y = abs(d-b)

if x == 0 or y == 0:
	print 0
	return

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

e = gcd(x,y)
x /= e
y /= e

print (x+y-1) * e