← 返回题目列表

Codeforces · 837/E

E. Vasya 的功能

中文机器翻译题面 查看原题

Vasya 正在学习数论。他将函数 f(a, b) 表示为:

- f(a, 0) = 0;
- f(a, b) = 1 + f(a, b - gcd(a, b)),其中 gcd(a, b) 是 a 和 b 的最大公约数。

Vasya 有两个数字 x 和 y,他想要计算 f(x, y)。他尝试自己做,但发现按照他想要的方式计算这个函数可能需要很长时间。所以他决定请你实现一个能够快速计算这个函数的程序。

输入

第一行包含两个整数 x 和 y (1 ≤ x, y ≤ 1012)。

输出

打印 f(x, y)。

示例

输入 #1

3 5

输出 #1

3

输入 #2

6 3

输出 #2

1