#include<cstdio>
#include<algorithm>
#include<cstring>
#define Nmax 5000005
using namespace std;
int n,i,j,d,f[Nmax],x,y,z,nr;
int sol;
int main()
{
    freopen("pascal.in","r",stdin);
    freopen("pascal.out","w",stdout);
    scanf("%d %d",&n,&d);
    if (d==4 || d==6) while (1);
    nr=n;
    memset(f,-1,sizeof(f));
    while (nr%d==0)
    x+=(nr/d),nr=nr/d;
    f[n]=x;
    f[0]=0;
    for (i=1;i<n;i++)
    {
        y=0; z=0;
        if (f[i]!=-1) y=f[i];
        else
        {
             nr=i;
             while (nr%d==0)
             y+=(nr/d),nr=nr/d;
             f[i]=y;
        }
        if (f[n-i]!=-1) z=f[n-i];
        else
        {
             nr=n-i;
             while (nr%d==0)
             z+=(nr/d),nr=nr/d;
             f[n-i]=z;
        }
        if (x>y+z)
        ++sol;
    }
    printf("%d",sol);
    return 0;
}