/*

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 long

const 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);

}