#include <bits/stdc++.h>
using namespace std;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
long long m, x, ans;
vector<long long> p;
int B = 1e4;
long long mult(long long a, long long b, long long M) {
  if (!b) return 0;
  return (mult(a, b / B, M) * B % M + a * (b % B)) % M;
}
long long power(long long base, long long to, long long M) {
  long long ret = 1;
  while (to) {
    if (to & 1) ret = mult(ret, base, M);
    to >>= 1;
    base = mult(base, base, M);
  }
  return ret;
}
long long find(long long a) {
  long long ret = 1;
  for (long long i = 2; i * i <= a; i++)
    if (a % i == 0) {
      ret *= i - 1;
      a /= i;
      long long temp = 1;
      while (a % i == 0) {
        ret *= i;
        a /= i;
      }
    }
  if (a != 1) ret *= a - 1;
  return ret;
}
long long len(long long x, long long m, long long M) {
  long long temp = m;
  for (long long i = 2; i * i <= temp; i++)
    if (temp % i == 0) {
      while (temp % i == 0) temp /= i;
      while (m % i == 0) {
        m /= i;
        if (power(x, m, M) != 1) {
          m *= i;
          break;
        }
      }
    }
  if (temp != 1 && power(x, m / temp, M) == 1) m /= temp;
  return m;
}
long long solve(long long a) {
  long long temp = find(a);
  return temp / len(x, temp, a);
}
int main() {
  scanf("%lld%lld", &m, &x);
  for (long long i = 1; i * i <= m; i++)
    if (m % i == 0) {
      ans += solve(i);
      if (m / i != i) ans += solve(m / i);
    }
  printf("%lld\n", ans);
}
