#include <fstream>

using namespace std;

long r, d, s[50000001], s1[50000002], pu[1000] ;

void citire() {
	ifstream fin("pascal.in");
	fin >> r >> d;
	fin.close();
}

void factori_primi(long s[], int d)  {
	long nr = 0;
	for (long p = d; p <= r; p *= d)
		pu[nr++] = p;
	for (int i = 2; i <= r; i ++) {		
		s[i] = 0;	
		for (long j = 0; pu[j] && pu[j] <= i; j++)
			s[i] += i/pu[j];
	}
}

long divizor (long r, long n) {
	switch (d) {
		case 2 :
		case 3 :
		case 5 :			
			return (s[r] - s[r - n] - s[n] > 0);
			break;										   
		case 4 : 
			return (s[r] - s[r - n] - s[n] > 1);
			break;				
		case 6 :
			return (s[r] - s[r - n] - s[n] > 0 && s1[r] - s1[r - n] - s1[n] > 0);
	}
	return 0;
}

long numar() {
	long nr = 0;
	for (long i = 1; i < (( r + 1) >> 1); i++)
		nr += divizor(r, i);
	nr <<= 1;
	if ( (r & 1) == 0 )
		nr += divizor(r, (r >> 1));

	return nr;
}

int main() {
	citire();
	if (d != 6 && d != 4)
		factori_primi(s, d);
	else 
		if (d == 4 )
			factori_primi(s, 2);
		else {
			factori_primi(s, 2);
			factori_primi(s1, 3);
		}

		ofstream fout("pascal.out");
		fout << numar();
		fout.close();

		return 0;
}