#include <fstream>
#define DIMN 50
#define DIM 5000001

using namespace std;

ifstream f("pascal.in");
ofstream g("pascal.out");

int p[DIMN];

bool ok[DIM];

int r, d, k, nr, nnr, sol;

int main () {
    f >> r >> d;
    if (d==2 || d==3 || d==5) {
        p[0] = 1;
        p[1] = d;
        k = 1;
        for (; p[k]<=r;)
            p[++k] = p[k-1] * d;
        nr = 0;
        for (int i=1; i<=k; ++i)
            nr += r/p[i];
        for (int i=0; i<=r; ++i) {
            nnr = 0;
            for (int j=1; j<=k; ++j)
                nnr += i/p[j] + (r-i)/p[j];
            if (nr > nnr)
                ++sol;
        }
        g << sol << "\n";
        return 0;
    }
    if (d == 4) {
        p[0] = 1;
        p[1] = 2;
        k = 1;
        for (; p[k]<=r;)
            p[++k] = p[k-1] * d;
        nr = 0;
        for (int i=1; i<=k; ++i)
            nr += r/p[i];
        for (int i=0; i<=r; ++i) {
            nnr = 0;
            for (int j=1; j<=k; ++j)
                nnr += i/p[j] + (r-i)/p[j];
            if (nr > nnr+1)
                ++sol;
        }
        g << sol << "\n";
        return 0;
    }
    if (d == 6) {
        p[0] = 1;
        p[1] = 2;
        k = 1;
        for (; p[k]<=r;)
            p[++k] = p[k-1] * d;
        nr = 0;
        for (int i=1; i<=k; ++i)
            nr += r/p[i];
        for (int i=0; i<=r; ++i) {
            nnr = 0;
            for (int j=1; j<=k; ++j)
                nnr += i/p[j] + (r-i)/p[j];
            if (nr > nnr)
                ok[i] = 1;
        }
        p[0] = 1;
        p[1] = 3;
        k = 1;
        for (; p[k]<=r;)
            p[++k] = p[k-1] * d;
        nr = 0;
        for (int i=1; i<=k; ++i)
            nr += r/p[i];
        for (int i=0; i<=r; ++i) {
            nnr = 0;
            for (int j=1; j<=k; ++j)
                nnr += i/p[j] + (r-i)/p[j];
            if (nr > nnr)
                ++sol;
        }
        g << sol << "\n";
    }
    return 0;
}