#include <bits/stdc++.h>
const long long mod = 100000000000031ll;
long long m, x, p[50], ans;
int k[50], c;
long long d(long long& a, long long b, bool t = 0) {
  if (b < 2 || a % b) return 1;
  long long r = b - 1;
  t ? 1 : k[c]++;
  for (a /= b; a % b == 0;) a /= b, t ? r *= b : k[c]++;
  t ? 1 : p[c++] = b;
  return r;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
unsigned long long mul(unsigned long long a, unsigned long long b,
                       unsigned long long p) {
  unsigned long long c = 0;
  for (; b; b >>= 17) c = (c + a * (b & 131071)) % p, a = (a << 17) % p;
  return c;
}
long long pw(long long a, long long n, long long p) {
  long long b = 1;
  for (; n; n >>= 1) n& 1 ? b = mul(b, a, p) : 1, a = mul(a, a, p);
  return b;
}
void dfs(int i, long long a, long long d, long long w) {
  if (i == c)
    (ans += mul(gcd(m, pw(x, a / d, m) - 1), w, mod)) %= mod;
  else
    for (int j = 0; j <= k[i]; j++)
      dfs(i + 1, a, d, w), d *= p[i], w *= p[i] - !j;
}
int main() {
  scanf("%lld%lld", &m, &x);
  long long a = m, b = d(a, 2, 1) * d(a, 3, 1);
  for (int i = 5; 1ll * i * i <= a; i += 6) b *= d(a, i, 1) * d(a, i + 2, 1);
  b *= d(a, a, 1);
  a = b;
  d(b, 2);
  d(b, 3);
  for (int i = 5; 1ll * i * i <= a; i += 6) d(b, i), d(b, i + 2);
  d(b, b);
  dfs(0, a, 1, 1);
  ans = mul(ans, pw(a, mod - 2, mod), mod);
  printf("%lld\n", ans);
}
