/*CodeForces - 837E - Vasya‘s Function [ 数论 ]  |  Educational Codeforces Round 26题意：	f(a, 0) = 0;	f(a, b) = 1 + f(a, b-gcd(a, b));	求 f(a, b) , a,b <= 1e12分析：	b 每次减 gcd(a, b) 等价于 b/gcd(a,b) 每次减 1	减到什么时候呢，就是  b/gcd(a,b)-k 后 不与 a 互质	可先将 a 质因数分解，b能除就除，不能除就减到最近的a的因子的倍数，即模拟整个过程		由于 a 至多只有 64个因子 （a <= 2^64） ，复杂度挺低*/#include <bits/stdc++.h>using namespace std;#define LL long longconst LL INF = 1e18;const int N = 1e5;LL a, b;map<LL, int> mp;map<LL, int>::iterator it;void GetFactors(LL x){    for (LL i = 2; i*i <= x; i++)    {        if (x % i == 0)        {            while (x % i == 0)            {                mp[i]++;                x /= i;            }        }    }    if (x != 1) mp[x] = 1;}int main(){    scanf("%lld%lld", &a, &b);    GetFactors(a);    LL ans = 0;    while (b)    {        for (it = mp.begin(); it != mp.end(); it++)        {            while ( (it->second) > 0 && b % (it->first) == 0)            {                b /= it->first;                --(it->second);            }        }        LL mi = INF, x = -1;        for (it = mp.begin(); it != mp.end(); it++)        {            if ((it->second) > 0 && b % (it->first) < mi)            {                mi = b % (it->first);                x = it->first;            }        }        if (x == -1)        {            ans += b; break;        }        ans += mi;        b -= mi;    }    printf("%lld\n", ans);}