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