#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << '{';
  for (int i = (0), __i = (((int)(vec).size())); i < __i; i++) {
    os << vec[i];
    if (i + 1 != ((int)(vec).size())) os << ',';
  }
  os << '}';
  return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &par) {
  os << '(' << par.first << ',' << par.second << ')';
  return os;
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : abs(x); }
template <class T>
T sqr(T x) {
  return x * x;
}
bool simp[1010101];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int i = (0), __i = (1010101); i < __i; i++) {
    simp[i] = true;
  }
  vector<int> smp;
  for (int i = (2), __i = (1010101); i < __i; i++) {
    if (simp[i]) {
      smp.push_back(i);
      for (long long j = (long long)i * i; j < 1010101; j += i) simp[j] = false;
    }
  }
  long long x, y;
  cin >> x >> y;
  vector<pair<long long, int>> fact;
  long long a = x;
  long long last = -1;
  for (int i = (0), __i = (((int)(smp).size())); i < __i; i++) {
    while ((a % smp[i]) == 0) {
      if (last == smp[i])
        fact[((int)(fact).size()) - 1].second++;
      else
        fact.push_back({smp[i], 1});
      a /= smp[i];
      last = smp[i];
    }
  }
  if (a > 1) fact.push_back({a, 1});
  a = x;
  long long b = y;
  long long res = 0;
  while (true) {
    long long g = gcd(a, b);
    if (g == b) {
      res++;
      break;
    }
    a /= g;
    b /= g;
    for (int i = (0), __i = (((int)(fact).size())); i < __i; i++) {
      while (g > 1 && fact[i].second > 0 && (g % fact[i].first) == 0) {
        fact[i].second--;
        g /= fact[i].first;
      }
    }
    long long cur = (b > a) ? b - a : b - 1;
    for (int i = (0), __i = (((int)(fact).size())); i < __i; i++) {
      if (fact[i].second > 0) {
        cur = min(cur, b - (b / fact[i].first) * fact[i].first);
      }
    }
    res += cur;
    b -= cur;
  }
  cout << res;
  return 0;
}
