#include <bits/stdc++.h>
using namespace std;
long long a, b;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int main() {
  while (scanf("%I64d%I64d", &a, &b) != EOF) {
    long long g = gcd(a, b);
    long long A = a / g;
    long long B = b / g;
    long long m = B;
    long long x = A;
    long long ans = 0;
    map<long long, long long> mp;
    for (long long i = 2; i * i <= x; i++) {
      if (A % i == 0) {
        while (A % i == 0) {
          if (mp.count(i) == 0)
            mp[i] = 1;
          else
            mp[i]++;
          A /= i;
        }
      }
    }
    if (A > 1) mp[A] = 1;
    while (B) {
      map<long long, long long>::iterator it = mp.begin();
      long long nn = 1;
      m = B;
      for (; it != mp.end(); it++) {
        long long n = it->first;
        if (it->second > 0) {
          long long mm = (B % n + n) % n;
          if (mm < m) {
            m = mm;
            nn = n;
          }
        }
      }
      ans += m;
      B -= m;
      B /= nn;
      mp[nn]--;
      if (mp[nn] == 0) mp.erase(nn);
    }
    printf("%I64d\n", ans);
  }
  return 0;
}
