#include<stdio.h>
long long s,i,n,m,d,nr,k,q;

long long exp(long long x,long long k)
{
	long long s=0;
	while(x/k)
	{
		s+=x/k;
		k*=d;
	}
	return s;
}


int main()
{
	freopen("pascal.in","r",stdin);
	freopen("pascal.out","w",stdout);
	scanf("%lld%lld",&n,&d);
	if (d==2||d==3||d==5)
	{
		k=exp(n,d);
	
		for (i=1;i<=n/2;i++)
			if (exp(i,d)+exp(n-i,d)<k) nr+=2;
		if (!(n%2)) if (exp(n/2,d)*2<k) nr--;
	}
	if (d==4)
	{
		k=exp(n,2);
	
		for (i=1;i<=n/2;i++)
			if (exp(i,2)+exp(n-i,2)+1<k) nr+=2;
		if (!(n%2)) if (2*exp(n/2,2)+1<k) nr--;
	}
	if (d==6)
	{
		k=exp(n,2);
		q=exp(n,3);
		
		for (i=1;i<=n/2;i++)
			if (exp(i,2)+exp(n-i,2)<k&&exp(i,3)+exp(n-i,3)<q) nr+=2;
		if (!(n%2)) if (2*exp(n/2,2)<k&&2*exp(n/2,3)<q) nr--;
	}
	printf("%lld\n",nr);
	return 0;
}