Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Вася изучает теорию чисел. Он определил функцию f(a, b) следующим образом:
f(a, 0) = 0;
f(a, b) = 1 + f(a, b - gcd(a, b)), где gcd(a, b) это наибольший общий делитель a и b.
У Васи есть два числа x и y, и он хочет вычислить f(x, y). Он хотел сделать это сам, но его способ может занять слишком много времени. Так что он просит вас написать программу, с помощью которой можно посчитать эту функцию быстро.
Входные данные
Первая и единственная строка содержит два целых числа x и y (1 ≤ x, y ≤ 1012).