#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);
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((v[n]>2*v[n/2]&&n%2==1)||v[n]<2*v[n/2])
      l*=2;
else
      l=2*l-1;
printf("%ld\n",l);
fclose(stdin);
fclose(stdout);
return 0;}