#include <fstream>
#include <vector>

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

long long n, p, s, cmmmc;
int x[20];
vector<int> divi;

void descomp(int x)
{
    if(x & 1) cmmmc = 1;
    else
    {
        cmmmc = 2, divi.push_back(2);
        do
        {
            x /= 2;
        }
        while(x % 2 == 0);
    }
    for(int d = 3; d * d <= x; d += 2)
        if(x % d == 0)
        {
            cmmmc *= d, divi.push_back(d);
            do
            {
                x /= d;
            }
            while(x % d == 0);
        }
    if(x > 1) cmmmc *= x,  divi.push_back(x);
}

void bt(int k, long long prod)
{
    for(int i = x[k - 1] + 1; i < divi.size(); ++i)
    {
        x[k] = i;
        long long t = prod * divi[i];
        s += ((k & 1) ? -cmmmc / t : cmmmc / t);
        bt(k + 1, t);
    }
}

int main()
{
    fin >> n >> p;
    descomp(n);
    s = cmmmc;
    x[0] = -1; //(*)
    bt(1, 1LL);
    fout << cmmmc / s*(p - 1) + 1;
    return 0;
}