Die Anzahl der Gitterpunkte auf einem Segment
Gegeben ist ein Segment, das und verbindet. Sie sollen bestimmen, wie viele Gitterpunkte (Punkte mit ganzzahligen Koordinaten) dieser Linienabschnitt durchläuft.
Bei der Berechnung der Gitterpunkte wird die Koordinate nicht in die Antwort einbezogen.
Eingabe
Die einzige Zeile der Eingabe enthält zwei ganze Zahlen
x und y (1 ≤ x, y ≤ ).Ausgabe
Das Programm soll die Anzahl der Gitterpunkte ausgeben, die dieser Linienabschnitt durchläuft.
Beispiele
Eingabe | Ausgabe |
8 12 | 4 |
12 8 | 4 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB