#include <fstream>

using namespace std;
long long n,b,t,d,e,ans, x;
long long gauss(long long n)
{
    return n*(n+1)/2;
}
long long apar(long long n, long long x)
{
    long long s=0,e=x;
    while(e<=n)
    {
        s+=e*gauss(n/e-1)+(n%e+1)*(n/e);
        e*=x;
    }
    return s;
}
int main()
{
    ifstream f("zero2.in");
    ofstream g("zero2.out");
    t=10;
    while(t)
    {
        t--;
        f>>n>>b;
        d=2;
        ans=-1;
        while(d*d<=b)
        {
            if(b%d==0)
            {
                e=1;
                b/=d;
                while(b%d==0)
                {
                    e++;
                    b/=d;
                }
                x=apar(n,d)/e;
                if(ans==-1||ans>x) ans=x;
            }
            d++;
        }
        if(b!=1)
        {
            x=apar(n, b);
            if(ans==-1||ans>x) ans=x;
        }
        g<<ans<<'\n';
    }
    f.close(); g.close();
    return 0;
}