Vasya's Function

题意翻译

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 <= 10^12) 输出格式： f(x, y)的值。 ------------ 第一次提翻译，求采纳。

题目描述

Vasya is studying number theory. He has denoted a function $ f(a,b) $ such that: - $ f(a,0)=0 $ ; - $ f(a,b)=1+f(a,b-gcd(a,b)) $ , where $ gcd(a,b) $ is the greatest common divisor of $ a $ and $ b $ . Vasya has two numbers $ x $ and $ y $ , and he wants to calculate $ f(x,y) $ . He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

输入输出格式

输入格式

The first line contains two integer numbers $ x $ and $ y $ ( $ 1<=x,y<=10^{12} $ ).

输出格式

Print $ f(x,y) $ .

输入输出样例

输入样例 #1

3 5

输出样例 #1

3

输入样例 #2

6 3

输出样例 #2

1