#include <bits/stdc++.h>
const long long N = 1000005;
long long m, a[N], f[N], p[N], n, cnt, x, ans;
std::map<long long, long long> id;
std::vector<long long> v;
void init() {
  for (long long i = 1; i * i <= m; i++)
    if (m % i == 0) {
      a[++n] = i;
      if (m / i != i) a[++n] = m / i;
    }
  std::sort(a + 1, a + n + 1);
  for (long long i = 1; i <= n; i++) id[a[i]] = i;
  long long x = m;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i) continue;
    p[++cnt] = i;
    while (x % i == 0) x /= i;
  }
  if (x > 1) p[++cnt] = x;
  for (long long i = 1; i <= n; i++) f[i] = m / a[i];
  for (long long i = 1; i <= cnt; i++)
    for (long long j = 1; j <= n; j++)
      if (a[j] % p[i] == 0) f[id[a[j] / p[i]]] -= f[j];
}
long long mul(long long x, long long y, long long mu) {
  x %= mu;
  y %= mu;
  long long ans = (x * y - (long long)((double)x * y / mu + 0.1) * mu) % mu;
  ans += ans < 0 ? mu : 0;
  return ans;
}
long long ksm(long long x, long long y, long long mu) {
  long long ans = 1;
  x = x % mu;
  for (; y; y >>= 1, x = mul(x, x, mu))
    if (y & 1) ans = mul(x, ans, mu);
  return ans;
}
bool MR(long long n) {
  if (n == 2 || n == 3 || n == 5 || n == 7) return 1;
  if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return 0;
  long long T = 12;
  long long d = n - 1, k = 0;
  while (d % 2 == 0) d >>= 1, k++;
  while (T--) {
    long long x = rand();
    x = ksm(x, d, n);
    if (x == 0) continue;
    for (long long i = 1; i <= k; i++) {
      long long t = x;
      x = mul(x, x, n);
      if (x == 1 && (t != 1 && t != n - 1)) return 0;
    }
    if (x != 1) return 0;
  }
  return 1;
}
long long gcd(long long x, long long y) {
  if (x % y == 0) return y;
  return gcd(y, x % y);
}
long long PR(long long n) {
  if (n % 2 == 0) return 2;
  if (n % 3 == 0) return 3;
  long long x = rand(), y = x, c = 12, step = 0, t = 1;
  while (++step) {
    y = (mul(y, y, n) + c) % n;
    if (x == y) return n;
    long long g = gcd((y - x + n) % n, n);
    if (g > 1) return g;
    if (step == t) x = y, t <<= 1;
  }
}
void find(long long n) {
  if (n == 1) return;
  if (MR(n)) {
    v.push_back(n);
    return;
  }
  long long d = n;
  while (d == n || d == 1) d = PR(n);
  while (n % d == 0) n /= d;
  find(d);
  find(n);
}
signed main() {
  srand(time(0));
  scanf("%lld%lld", &m, &x);
  init();
  for (long long i = 1; i < n; i++) {
    long long t = m / a[i], c = f[id[a[i]]];
    v.clear();
    find(c);
    std::sort(v.begin(), v.end());
    std::unique(v.begin(), v.end());
    for (auto j : v)
      while (c % j == 0 && ksm(x, c / j, t) == 1) c /= j;
    ans = ans + f[i] / c;
  }
  printf("%lld\n", ans + 1);
}
