#include <fstream>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
long long n, b, k, nr, sol, x;

long long formula(long long n)
{
    return n * (n + 1) / 2;
}

long long count(long long n, long long a)
{
    long long s = 0, nr = a;
    while(nr <= n)
    {
        s += nr * formula(n / nr - 1) + (n % nr + 1) * (n / nr);
        nr *= a;
    }
    return s;
}

void solve()
{
	k = 2;
	sol = -1;
	while(k * k <= b)
	{
		if(b % k == 0)
		{
			nr = 1;
			b /= k;
			while(b % k == 0)
			{
				nr++;
				b /= k;
			}
			x = count(n, k) / nr;
			if(sol == -1 || sol > x) 
				sol = x;
		}
		if(k == 2)
			k++;
		else
			k += 2;
	}
	if(b != 1)
	{
		x = count(n, b);
		if(sol == -1 || sol > x) 
			sol = x;
	}
}

int main()
{
	int t;
	t = 10;
	while(t--)
	{
		f >> n >> b;
		solve();
		g << sol << '\n';
	}
}