#include<stdio.h>
#define N 5000001
long n,l=0,i,t=0,v[N],r,j;
int k;
int main()
{freopen("pascal.in","r",stdin);
freopen("pascal.out","w",stdout);
scanf("%ld%d\n",&n,&k);
if(k==2)
       {for(r=1;r<=n;r++)
              {j=r;
              while((j&1)==0)
                     {t++;
                     j=j>>1;}
              v[r]=t;}}
else
       {for(r=1;r<=n;r++)
              {j=r;
              while(j%k==0)
                     {t++;
                     j/=k;}
              v[r]=t;}}
for(i=1;i<=n/2;i++)
if(v[n]>v[i]+v[n-i])
       l++;
if(n%2==1)
       l*=2;
else
       l=2*l-1;
printf("%ld\n",l);
fclose(stdin);
fclose(stdout);
return 0;}