#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
bool flag[1000010];
int p[1000010];
long long Gcd(long long x, long long y) { return y ? Gcd(y, x % y) : x; }
long long F(long long x, long long y) {
  if (y == 0) return 0;
  if (x % y == 0) return 1;
  if (y % x == 0) return y / x;
  long long d = Gcd(x, y), a = x / d, b = y / d;
  long long t = a, Min = b - 1;
  for (int i = 1; i <= p[0] && p[i] <= a; ++i) {
    if (t % p[i] == 0) {
      Min = min(Min, b % p[i]);
      while (t % p[i] == 0) t /= p[i];
    }
  }
  if (t != 1) Min = min(Min, b % t);
  return Min + F(x, (b - Min) * d);
}
int main() {
  for (int i = 2; i < 1000010; ++i) {
    if (!flag[i]) p[++p[0]] = i;
    for (int j = 1; j <= p[0] && i * p[j] < 1000010; ++j) {
      flag[i * p[j]] = true;
      if (i % p[j] == 0) break;
    }
  }
  long long x, y;
  cin >> x >> y;
  printf("%I64d\n", F(x, y));
  return 0;
}
