Counting Euclid's Steps

Difficulty: 1200 2000 ms 128 MB

math

Run Euclid's algorithm on (A, B): repeatedly replace (a, b) by (b, a mod b) until b = 0. Print how many replacement steps happen.

Input: one line with two integers A and B.

Output: the number of steps until b becomes 0.

Constraints:

• 1 ≤ A, B ≤ 10¹⁸

Sample Tests

48 18

3

7 7

1

Read the Editorial