#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pascal.in");
ofstream cout("pascal.out");
int n,m;
int maxi=-1;
vector<int> V;
void putere()
{
    int aux=m,nr=0,p=1;
    while(aux%2==0)
    {
        aux=aux/2;
        p=p*2;
        nr++;
    }
    if(nr)
      maxi=max(maxi,p);
    for(int i=3;i*i<=aux;i=i+2)
    {
      nr=0;
      p=1;
      while(aux%i==0)
      {
          aux=aux/i;
          nr++;
          p=p*i;
      }
      if(nr)
        maxi=max(p,maxi);
    }
    if(aux>1)
       maxi=max(maxi,aux);
}
int nz(int n)
{
    int s=0;
    int p=maxi;
    while(p<=n)
    {
        s=s+n/p;
        p=p*m;
    }
    return s;
}
int main()
{
    cin>>n>>m;
    putere();
    V.resize(n+1);
    for(int i=0;i<=n;i++)
       V[i]=nz(i);
    int nr=0 ;
    for(int i=0;i<=n;i++)
         if(V[i]+V[n-i]<V[n])
        nr++;
    cout<<nr;
    return 0;
}