CODE FESTIVAL 2016 Relay (Parallel)

E - 方眼紙と線分 / Segment on Grid Paper


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 100

問題文

高橋君は方眼紙の上に線分を書くことにしました。

方眼紙のあるマスを起点として、右に x マス、上に y マス進んだところにあるマスをマス (x, y) と呼びます。

マス (A, B) の左下の点と マス (C, D) の左下の点を結んで線分を書くとき、線分が横切るマスの個数を求めてください。

ただし、線分があるマスの内側(境界は含まない)を通るとき、「線分がそのマスを横切る」と言います。

制約

  • 1 \leq A, B, C, D \leq 10^9
  • A \neq C もしくは B \neq D の少なくとも一方が成り立つ。

入力

入力は以下の形式で標準入力から与えられる。

A B C D

出力

線分が横切るマスの個数を出力せよ。


入力例 1

1 1 3 4

出力例 1

4

入力例 2

2 3 10 7

出力例 2

8

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

Submit提出する